LC4 Median of Two Sorted Arrays

Problem

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:

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

The median is 2.0

Example 2:

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

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

由于nums1和nums2都是有序的，所以对这两个数组，一定存在一个分割，使得在分割左半边的nums1和nums2的长度等于右边，且满足左边的最大值小于右边的最小值。

设nums1分割位于nums1[i - 1]和nums1[i]之间，nums2分割位于nums2[j - 1]和nums2[j]之间，且有

{nums1[i−1]<nums2[j]nums2[j−1]<nums1[i]i+j==m−i+n−j,if m+n is eveni+j==m−i+n−j+1,if m+n is odd\begin{cases}nums1[i - 1] < nums2[j]\\nums2[j - 1] < nums1[i]\\i + j == m-i+n-j,if\ m+n\ is\ even\\i + j == m-i+n-j+1,if\ m+n\ is\ odd\end{cases}

设left和right来对nums1进行二分，二分的条件即为上述关系式1&2。

最后根据m+n的奇偶情况判断应该返回maxLeft还是(maxLeft + minRight) / 2。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
    int m = nums1.size(), n = nums2.size();
    if(m > n) return findMedianSortedArrays(nums2, nums1);
    int left = 0, right = m, halfLen = (m + n + 1) / 2;
    while(left <= right){
        int i = left + (right - left) / 2;
        int j = halfLen - i;
        if(i > left && nums1[i - 1] > nums2[j]){
            right = i - 1;
        }
        else if(i < right && nums2[j - 1] > nums1[i]){
            left = i + 1;
        }
        else{
            int maxLeft = 0;
            if(i == 0) maxLeft = nums2[j - 1];
            else if(j == 0) maxLeft = nums1[i - 1];
            else maxLeft = max(nums1[i - 1], nums2[j - 1]);
            if((m + n) % 2 == 1) return maxLeft;

            int minRight = 0;
            if(i == m) minRight = nums2[j];
            else if(j == n) minRight = nums1[i];
            else minRight = min(nums2[j], nums1[i]);
            return (maxLeft + minRight) / 2.0; 
        }
    }
    return 0.0;
}

LC29 Divide Two Integers

Problem

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator.

Return the quotient after dividing dividend by divisor.

The integer division should truncate toward zero, which means losing its fractional part. For example, truncate(8.345) = 8 and truncate(-2.7335) = -2.

Example 1:

1
2
3
Input: dividend = 10, divisor = 3
Output: 3
Explanation: 10/3 = truncate(3.33333..) = 3.

Example 2:

1
2
3
Input: dividend = 7, divisor = -3
Output: -2
Explanation: 7/-3 = truncate(-2.33333..) = -2.

Note:

  • Both dividend and divisor will be 32-bit signed integers.
  • The divisor will never be 0.
  • Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.
Think
  • Approach 1

设被除数为dividend，除数为divisor，初始化结果res=0

当dividend >= divisor的时候，找到当前最大的n满足divisor∗2n<=dividenddivisor * 2^n <= dividend，res += n，然后在dividend上减去divisor∗2ndivisor * 2^n，进行下一次循环；

由于int的范围为[−231,231][-2^{31}, 2^{31}]，如果一正一负，可能会导致一开始的结果溢出，所以需要将被除数和除数都转化为负数，然后再进行上述计算。

  • Approach 2

在Approach 1的基础上，首先将除数的所有小于被除数的2的幂次乘积存储在数组里，然后直接去读取数组即可。

Code
  • Approach 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int HALF_INT_MIN = -1073741824;
int divide(int dividend, int divisor) {
    if(dividend == INT_MIN && divisor == -1){
        return INT_MAX;
    }
    int negatives = 2;
    if(dividend > 0){
        dividend = -dividend;
        negatives--;
    }
    if(divisor > 0){
        divisor = -divisor;
        negatives--;
    }
    int res = 0;
    while(dividend <= divisor){
        int powerOfTwo = -1;
        int value = divisor;
        while(value >= HALF_INT_MIN && value + value >= dividend)
        {
            value += value;
            powerOfTwo += powerOfTwo;
        }
        res += powerOfTwo;
        dividend -= value;
    }
    return negatives != 1 ? -res: res;
}
  • Approach 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int HALF_INT_MIN = -1073741824;
int divide(int dividend, int divisor) {
    if(dividend == INT_MIN && divisor == -1){
        return INT_MAX;
    }
    int negatives = 2;
    if(dividend > 0){
        dividend = -dividend;
        negatives--;
    }
    if(divisor > 0){
        divisor = -divisor;
        negatives--;
    }
    int tmp = -1;
    vector<int> dou;
    vector<int> powerOfTwo;
    while(divisor >= dividend){
        dou.push_back(divisor);
        powerOfTwo.push_back(tmp);
        if(divisor < HALF_INT_MIN){
            break;
        }
        divisor += divisor;
        tmp += tmp;
    }
    int res = 0;
    for(int i = dou.size() - 1; i >= 0; i--){
        if(dou[i] >= dividend){
            dividend -= dou[i];
            res += powerOfTwo[i];
        }
    }
    return negatives != 1 ? -res: res;
}

LC33 Search in Rotated Sorted Array

Problem

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

Example 1:

1
2
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4

Example 2:

1
2
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
Think

二分，初始化left=0，right=n - 1

当left < right的时候，

如果nums[mid] == target，则直接返回mid，

如果nums[mid] < taget，通过和nums[left]比较来判断mid当前是在左上升区间还是右上升区间

如果nums[mid] > taget，通过和nums[left]比较来判断mid当前是在左上升区间还是右上升区间

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
int search(vector<int>& nums, int target) {
    if(nums.empty()) return -1;
    int left = 0, right = nums.size() - 1;
    while(left < right){
        int mid = left + (right - left) / 2;
        if(nums[mid] == target){
            return mid;
        }
        else if(nums[mid] < target){
            if(nums[mid] < nums[left]){
                if(target < nums[left]){
                    left = mid + 1;
                }
                else{
                    right = mid - 1;
                }
            }
            else{
                left = mid + 1;
            }
        }
        else{
            if(nums[mid] >= nums[left]){
                if(target < nums[left]){
                    left = mid + 1;
                }
                else{
                    right = mid - 1;
                }
            }
            else{
                right = mid - 1;
            }
        }
    }
    return nums[left] == target ? left : -1;
}

LC34 Find First and Last Position of Element in Sorted Array

Problem

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

1
2
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

1
2
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
Think

分两次二分查找，分别查找左端点和右端点

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
vector<int> searchRange(vector<int>& nums, int target) {
    vector<int> res = {-1, -1};
    int left = findRange(nums, target, true);
    if(left == nums.size() || nums[left] != target){
        return res;
    }
    res[0] = left;
    res[1] = findRange(nums, target, false) - 1;
    return res;
}
int findRange(vector<int>& nums, int target, bool leftOrRight){
    int left = 0, right = nums.size();
    while(left < right){
        int mid = left + (right - left) / 2;
        if(nums[mid] > target || (leftOrRight && nums[mid] == target)){
            right = mid;
        }
        else{
            left = mid + 1;
        }
    }
    return left;
}

LC35 Search Insert Position

Problem

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

1
2
Input: [1,3,5,6], 5
Output: 2

Example 2:

1
2
Input: [1,3,5,6], 2
Output: 1

Example 3:

1
2
Input: [1,3,5,6], 7
Output: 4

Example 4:

1
2
Input: [1,3,5,6], 0
Output: 0
Think

普通的二分，如果不在数组里，则插入的位置恰好就是最终left = right的位置。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int searchInsert(vector<int>& nums, int target) {
    int left = 0, right = nums.size();
    while(left < right){
        int mid = left + (right - left) / 2;
        if(nums[mid] == target){
            return mid;
        }
        else if(nums[mid] > target){
            right = mid;
        }
        else{
            left = mid + 1;
        }
    }
    return left;
}

LC50 Pow(x, n)

Problem

Implement pow(x, n), which calculates x raised to the power n (xn).

Example 1:

1
2
Input: 2.00000, 10
Output: 1024.00000

Example 2:

1
2
Input: 2.10000, 3
Output: 9.26100

Example 3:

1
2
3
Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Note:

  • -100.0 < x < 100.0
  • n is a 32-bit signed integer, within the range [−231, 231 − 1]
Think

二分，注意INT_MIN在变成正数时会溢出，需要先+1处理一下

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
double myPow(double x, int n) {
    if(n < 0){
        return (1 / myPow(x, -(n + 1))) / x;
    }
    while(n){
        double tmp = myPow(x, n / 2);
        if(n % 2 == 1){
            return x * tmp * tmp;
        }
        else{
            return tmp * tmp;
        }
    }
    return 1;
}

LC69 Sqrt(x)

Problem

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

1
2
Input: 4
Output: 2

Example 2:

1
2
3
4
Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.
Think

二分法，设置left和right，表示结果在[left, right]内

如果mid*mid=target则直接返回，如果mid*mid<target，说明结果应该在[mid+1, right]内，否则结果应该在[left, mid-1]内。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int mySqrt(int x) {
    if(x == 0) return 0;
    if(x == 1) return 1;
    int left = 0, right = x;
    while(left < right){
        int mid = left + (right - left) / 2;
        if(mid == x / mid && x % mid == 0){
            return mid;
        }
        else if(mid > x / mid){
            right = mid;
        }
        else{
            left = mid + 1;
        }
    }
    return left - 1;
}

LC74 Search a 2D Matrix

Problem

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

Example 1:

1
2
3
4
5
6
7
8
Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
Output: true

Example 2:

1
2
3
4
5
6
7
8
Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
Output: false
Think

二分，初始left=0，right=m * n即可。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool searchMatrix(vector<vector<int>>& matrix, int target) {
    if(matrix.empty() || matrix[0].empty()) return false;
    int m = matrix.size(), n = matrix[0].size();
    int left = 0, right = m * n;
    while(left < right){
        int mid = left + (right - left) / 2;
        int row = mid / n;
        int col = mid % n;
        if(matrix[row][col] == target) return true;
        else if(matrix[row][col] < target) left = mid + 1;
        else right = mid;
    }
    return false;
}

LC81 Search in Rotated Sorted Array II

Problem

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).

You are given a target value to search. If found in the array return true, otherwise return false.

Example 1:

1
2
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true

Example 2:

1
2
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false

Follow up:

  • This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.
  • Would this affect the run-time complexity? How and why?
Think

在LC33-Search-in-Rotated-Sorted-Array的基础上，注意判断一下当前nums[mid]=num等于nums[left]的时候，这个时候mid可能在左上升区间也可能在右上升区间，所以此时只能将left+1，相当于跳过最左端的部分。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
bool search(vector<int>& nums, int target) {
    if(nums.empty()) return false;
    int left = 0, right = nums.size();
    while(left < right){
        int mid = left + (right - left) / 2;
        int num = nums[mid];
        if(num == target) return true;
        else if(num < target){
            if(num == nums[left]) left += 1;
            else if(num > nums[left]) left = mid + 1;
            else{
                if(target == nums[left]) return true;
                else if(target > nums[left]) right = mid;
                else left = mid + 1;
            }
        }
        else{
            if(num == nums[left]) left += 1;
            else if(num > nums[left]){
                if(target == nums[left]) return true;
                else if(target > nums[left]) right = mid;
                else left = mid + 1;
            }
            else right = mid;
        }
    }
    return false;
}

LC153 Find Minimum in Rotated Sorted Array

Problem

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

You may assume no duplicate exists in the array.

Example 1:

1
2
Input: [3,4,5,1,2] 
Output: 1

Example 2:

1
2
Input: [4,5,6,7,0,1,2]
Output: 0
Think

二分，设置left和right，我们要找的分界点的特点是大于其右边的值，范围为[left, right]，因此有：

当nums[mid] < nums[right]的时候，说明mid在右上升区间，因此right = mid；

当nums[mid] > nums[right]的时候，说明mid在左上升区间，因此left = mid + 1；

注意这里只能和nums[right]比较，因为nums[right]一定在右上升区间上，但是left可能不在左上升区间上。

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
int findMin(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while(left < right){
        int mid = left + (right - left) / 2;
        if(nums[mid] < nums[right]){
            right = mid;
        }
        else{
            left = mid + 1;
        }
    }
    return nums[left];
}

LC154 Find Minimum in Rotated Sorted Array II

Problem

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

Find the minimum element.

The array may contain duplicates.

Example 1:

1
2
Input: [1,3,5]
Output: 1

Example 2:

1
2
Input: [2,2,2,0,1]
Output: 0

Note:

Think

二分法，在LC153 Find Minimum in Rotated Sorted Array的基础上，当nums[mid] == nums[right]的时候，根据上题分析，left可能不在左上升区间上，此时left即为要求的结果，而right必定不可能为要求解的结果，因此此处将right -= 1即可，而不可以left += 1.

Code 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int findMin(vector<int>& nums) {
    int left = 0, right = nums.size() - 1;
    while(left < right){
        int mid = left + (right - left) / 2;
        if(nums[mid] < nums[right]){
            right = mid;
        }
        else if(nums[mid] > nums[right]){
            left = mid + 1;
        }
        else{
            right -= 1;
        }
    }
    return nums[left];
}

LC167 Two Sum II - Input array is sorted

Problem

Given an array of integers that is already *sorted in ascending order*, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

Note:

  • Your returned answers (both index1 and index2) are not zero-based.
  • You may assume that each input would have exactly one solution and you may not use the same element twice.

Example:

1
2
3
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.
Think
  • Approach 1

二分，确定一个找另一个

  • Approach 2

双指针，nums[left]+nums[right] > target的时候right–，< target的时候left++；

Code
  • Approach 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
vector<int> twoSum(vector<int>& numbers, int target) {
    int n = numbers.size();
    for(int i = 0; i < n && numbers[i] <= target / 2; i++){
        int index = findTarget(numbers, i, target - numbers[i]);
        if(index != -1){
            return {min(i + 1, index + 1), max(i + 1, index + 1)};
        }
    }
    return {-1, -1};
}
int findTarget(vector<int>& numbers, int start, int target){
    int left = start + 1, right = numbers.size() - 1;
    while(left <= right){
        int mid = left + (right - left) / 2;
        if(numbers[mid] == target){
            return mid;
        }
        else if(numbers[mid] > target){
            right = mid - 1;
        }
        else{
            left = mid + 1;
        }
    }
    return -1;
}
  • Approach 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> twoSum(vector<int>& nums, int target) {
    int n = nums.size();
    int left = 0, right = n - 1;
    while(left < right){
        int tmp = nums[left] + nums[right];
        if(tmp < target){
            left++;
        }
        else if(tmp > target){
            right--;
        }
        else{
            return {left + 1, right + 1};
        }
    }
    return {-1, -1};
}

Review

对于二分搜索的题目来说，最重要的是

  • 确定left和right的初值；
  • 确定我们要求的值是在[left, right]还是[left, right)；
  • 内部分至少三种情况，f(mid) == target，f(mid) < target，f(mid) > target，注意这里就算f(mid) == target也不一定代表可以直接返回结果，因为可能存在相同值的情况；
  • 循环结束，如果循环的条件是left <= right，则循环 结束代表没有找到需要的值；如果循环的条件是left < right，则需要单独判断一下left=right处的值是否符合条件。