个人技术分享

704. 二分查找

class Solution {
public:
    int search(vector<int>& nums, int target) {
        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) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        return -1;
    }
};

278. 第一个错误的版本

// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (!isBadVersion(mid)) {
                left =  mid + 1; 
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
};

977. 有序数组的平方

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int len = nums.size();
        int left = 0, right = len - 1;
        
        vector<int> res(len);
        for (int i = len - 1; i >= 0; --i) {
            int leftVal = nums[left] * nums[left];
            int rightVal = nums[right] * nums[right];
            if (leftVal > rightVal) {
                res[i] = leftVal;
                left++;
            } else {
                res[i] = rightVal;
                right--;
            }
        }
        return res;
    }
};

35. 搜索插入位置

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        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) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            }
        }
        // 二分没有找到插入的位置, 那么target 一定小于 left, 从left 位置插入既能满足题解。
        return left;
    }
};

34. 在排序数组中查找元素的第一个和最后一个位置

class Solution {
public:
    int leftBound(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid  = left + (right - left) / 2;
            if (nums[mid] == target) {
                right = mid - 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1; 
            }
        }

        // left越界，则不存在
        if (left >= nums.size()) {
            return -1;
        }
        return nums[left] == target ? left : -1;
    }

    int rightBound(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid  = left + (right - left) / 2;
            if (nums[mid] == target) {
                left = mid + 1;
            } else if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1; 
            }
        }
        // right越界，则不存在
        if (right < 0) {
            return -1;
        }
        return nums[right] == target ? right : -1;
    }

    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) {
            return vector<int>({-1, -1});
        }
        int left = leftBound(nums, target);
        int right = rightBound(nums, target);
        return vector<int>({left, right});
    }
};

153. 寻找旋转排序数组中的最小值

旋转排序数组需要 和 right对比

class Solution {
public:
    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]) {
                left = mid + 1;
            } else if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else if (nums[mid] < nums[right]) {
                right = mid;
            }
        }
        return nums[right];
    }
};

33. 搜索旋转排序数组

寻找最小值的下标，分段处理，注意边界

旋转排序数组需要 和 right对比

class Solution {
public:
    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]) {
                left = mid + 1;
            } else if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else if (nums[mid] < nums[right]) {
                right = mid;
            }
        }
        return right;
    }

    int bsearch(vector<int>& nums, int left, int right, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else if (nums[mid] > target) {
                right = mid - 1;
            } else if (nums[mid] == target) {
                return mid;
            }
        }
        return -1;
    }

    int search(vector<int>& nums, int target) {
        int minIndex = findMin(nums);
        if (minIndex == 0) {
            return bsearch(nums, minIndex, nums.size() - 1, target);
        } else if (nums[0] < target) {
            return bsearch(nums, 0, minIndex - 1, target);
        } else if (nums[0] > target) {
            return bsearch(nums, minIndex, nums.size() - 1, target);
        } else {
            return 0;
        }
    }
};

直接二分查找，注意边界

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] < nums[right]) {
                if (target > nums[mid] && target <= nums[right]) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else {
                if (target >= nums[left] && target < nums[mid]) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return -1;
    }
};

74. 搜索二维矩阵

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();
        int low = 0, high = m * n - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            int val = matrix[mid / n][mid % n];
            if (val == target) {
                return true;
            } else if (val < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return false;
    }
};

4. 寻找两个正序数组的中位数

class Solution {
public:
    double getKth(vector<int>& nums1, int start1, int end1, vector<int>& nums2, int start2, int end2, int k) {
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        if (len1 > len2) {
            return getKth(nums2, start2, end2, nums1, start1, end1, k);
        }

        if (len1 == 0) {
            return nums2[start2 + k - 1];
        }

        if (k == 1) {
            return min(nums1[start1], nums2[start2]);
        }

        // 每次减少k/2
        int mid1 = start1 + min(len1, k / 2) - 1;
        int mid2 = start2 + min(len2, k / 2) - 1;

        if (nums1[mid1] < nums2[mid2]) {
            return getKth(nums1, mid1 + 1, end1, nums2, start2, end2, k - (mid1 - start1 + 1));
        } else {
            return getKth(nums1, start1, end1, nums2, mid2 + 1, end2, k - (mid2 - start2 + 1));
        }
    }
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        int k1 = (m + n + 1) / 2;
        int k2 = (m + n + 2) / 2;
        return (getKth(nums1, 0, m - 1, nums2, 0, n - 1, k1) + getKth(nums1, 0, m - 1, nums2, 0, n - 1, k2)) * 0.5;
    }
};