数组问题-LeetCode1、4（哈希表、归并排序）
数组问题-LeetCode1、4（哈希表、归并排序）
作者：TeddyZhang
公众号：算法工程师之路
数组问题：LeetCode #1 #4
编程题
【LeetCode #1】两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
解题思路：
这个题目使用哈希表可以将算法优化到O(n), 这里面我们只需要遍历一遍哈希表，有一个优化的思路，就是哈希表边创建边查找。其中键值key为数组nums的元素，而value为数组nums的元素的索引。因此当我们遍历到nums[i]时，我们就需要去哈希表中查找target-nums[i]，从而得到其索引，因此res将i和hashmap[target-nums[i]]放入数组中！
CPP源码
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hashmap;
vector<int> res;
for(int i = ;i < nums.size();i++){
if(hashmap.count(target-nums[i]) > ){
// 比使用hashmap.find(target-nums[i] != hashmap.end())快一点
res.push_back(hashmap[target-nums[i]]);
res.push_back(i);
return res;
}
hashmap[nums[i]] = i;
}
return res;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/two-sum/
【LeetCode #4】寻找两个有序数组的中位数
给定两个大小为 m 和 n 的有序数组nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3] nums2 = [2]
则中位数是 2.0 示例 2:
nums1 = [1, 2] nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
解题思路： 比较简单的思路使用归并排序，为什么有这个思路呢？因为题目说两个数组是有序数组，因此我们对两个数组进行merge，如果小的数则放入res数组中，直到res的数组大小为(m*n)/2+1，因此最后在总个数为偶数时，中位数为res中最后两个数求平均，否则中位数为res数组中最后一个数。
至于O(log(m+n))的方法，大家可以看官方题解，此处不再赘述！！！
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
vector<int> res;
int m = nums1.size(), n = nums2.size();
int mid = (m + n) / + ;
int i, j;
for(i = , j = ;i <m && j < n;){
if(nums1[i] > nums2[j]){
res.push_back(nums2[j++]);
}
else if(nums1[i] <= nums2[j]){
res.push_back(nums1[i++]);
}
if(res.size() == mid){
break;
}
}
while(res.size() != mid){
if(i < m)
res.push_back(nums1[i++]);
if(j < n)
res.push_back(nums2[j++]);
}
int len = res.size();
if((m + n) % == )
return (res[len-1] + res[len-2]) / 2.0;
return res[len-1];
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays
完