leetcode刷題-Array#1

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
           

• 思路1：two pointers從兩邊找。比 target 大右指針向左（變小）。比 target 小左指針向右（變大）。
• 注意：
  • 題目沒說排序了，是以要提前排序
  • 因為排序就就全亂了，是以要記錄數和index的關系
• 複雜度：時間O(log n), 空間O(n)

struct Pair{
  int num;
  int index;
};
int compare(Pair &a, Pair &b) {
    return a.num < b.num;
}
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int l = 0, r = nums.size() - 1;
        vector<Pair> pairs(nums.size(), {0, 0});
        for(int i = 0; i < nums.size(); i++) {
            pairs[i].num = nums[i];
            pairs[i].index = i;
        }
        sort(pairs.begin(), pairs.end(), compare);
        while(l < r) {
            if(pairs[l].num + pairs[r].num > target) {
                r--;
            } else if(pairs[l].num + pairs[r].num < target) {
                l++;
            } else {
                break;
            }
        }
        return {pairs[l].index, pairs[r].index};
    }
};
           

• 思路2 ：我沒想出來，是從别人那裡看的。因為保證都存在，是以呢，就往後掃描。把之前的數和index存在map裡面。每次在 i 這個位置，就需要一個want = target - num[i] 來湊。want如果存在于map中，傳回index即可。我覺得這個思路主要是利用了題目裡保證一定有一對數。考慮到有可能重複。是以就每掃描一個數，往map裡存一個數。
• 複雜度：時間空間都是O(n)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> numIndex;
        for(int i = 0; i < nums.size(); i++) {
            int want = target - nums[i];
            if(numIndex.find(want) != numIndex.end()) {
                return {numIndex[want], i};
            }
            numIndex[nums[i]] = i;
        }
        return {0, 0};
    }
};
           

4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0
           

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5
           

• 思路：這題目一開始沒有思路，看了看youtube Hua Hua的講解視訊才明白。
  • 兩個數組，長度為n1, n2
  • 則中位數在 k = (n1 + n2 + 1) / 2 處(如果合成一個數組)。
  • 兩個數組的可能中間值C[k-1] 和 C[k] 一定從A[m1 - 1], A[m1], B[m2 -1], B[M2]中産生
  • C[k-1] < C[k], 是以 A[m1-1], B[m2-1] < A[m1], B[m2]
  • 是以二分搜尋的條件就是
    • A[m1] < B[m2 - 1] , l = m1 + 1
    • else， r = m1
  • 隻需對小的數組進行二分搜尋即可
• 注意：
  • 如果二分搜尋超出了數組的界限，則說明整個數組都比另一個數組大或小，這樣中值不會出現在目前數組中。
  • 二分搜尋那裡是關鍵。

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size();
        int n2 = nums2.size();
        if(n1 > n2) return findMedianSortedArrays(nums2, nums1);
        
        int k = (n1 + n2 + 1) / 2;
        int l = 0, r = n1;
        
        while(l < r) {
            int m1 = (l + r) / 2;
            int m2 = k - m1;
            if(nums1[m1] < nums2[m2 - 1]) {
                l = m1 + 1;
            } else {
                r = m1;
            }
        }
        
        int m1 = l;
        int m2 = k - l;
        
        int c1 = max( m1 <= 0 ? INT_MIN : nums1[m1 - 1],
                      m2 <= 0 ? INT_MIN : nums2[m2 - 1]);
        
        if ((n1 + n2) % 2 == 1)
            return c1;
        
        int c2 = min( m1 >= n1 ? INT_MAX : nums1[m1],
                      m2 >= n2 ? INT_MAX : nums2[m2]);
        
        return (c1 + c2) * 0.5;
    }
};