LeetCode-binary search类总结(会持续更新的...)

算法 评论

本文主要是对leetcode中的binary search类算法的总结，包含了各题的solution和常用的解决方法。

相关源码：code

1
2
3
关于二分查找的一些trick：
1. mid=lo+(hi-lo)/2,防止大数溢出；
2. 注意区分两种搜索空间：index search | range search;

278. First Bad Version

Description:

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

解题思路：本题数组为有序 ，并且题目要求查找 ，自然而然会想到二分查找，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool isBadVersion(int version);
class Solution {
public:
    int firstBadVersion(int n) {
        int front = 1;
        int tail = n;
        while(true){
            int mid = (tail-front)/2 + front;
            bool res = isBadVersion(mid);
            if(res){
                if(!isBadVersion(mid-1)) return mid;
                tail = mid-1;
            }else{
                front = mid+1;
            }
        }
    }
};

222. Count Complete Tree Nodes

Description:

Given a complete binary tree, count the number of nodes.

Definition of a complete binary tree from Wikipedia:
In a complete binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between 1 and 2h nodes inclusive at the last level h.

解题思路：基本思路就是树的遍历，利用完全二叉树的性质优化程序，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int countNodes(TreeNode* root) {
        if(!root) return 0;
        int l=0, r=0;
        TreeNode *lp=root, *rp=root;
        while(lp){l++; lp=lp->left;}
        while(rp){r++; rp=rp->right;}
        if(l==r) return pow(2,l)-1;
        return countNodes(root->left)+countNodes(root->right)+1;
    }
};

29. Divide Two Integers

Description:

Divide two integers without using multiplication, division and mod operator.

If it is overflow, return MAX_INT.

解题思路：利用减法，加之移位 操作优化 ，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int divide(int dividend, int divisor) {
        if(!divisor || (dividend==INT_MIN && divisor==-1)){
            return INT_MAX;
        }
        int res=0;
        int sign = (dividend<0)^(divisor<0)?-1:1;
        long long divid=labs(dividend);
        long long divis=labs(divisor);
        while(divid>=divis){
            long long temp=divis, multi=1;
            while(divid>=(temp<<1)){
                multi<<=1;
                temp<<=1;
            }
            divid-=temp;
            res +=multi;
        }
        return sign==1?res:0-res;
    }
};

33. Search in Rotated Sorted Array

Description: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.

解题思路：经典题型 ，先找到最小值的位置，然后“平移”数组，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.size()==0) return -1;
        int l=0;
        int r=nums.size()-1;
        while(l<r){
            int mid=(r+l)/2;
            if(nums[mid]>nums[r]) l=mid+1;
            else r=mid;
        }
        int rot=l;
        l=0,r=nums.size()-1;
        while(l<=r){
            int mid=(l+r)/2;
            int realmid=(mid+rot)%nums.size();
            if(nums[realmid]==target) return realmid;
            if(nums[realmid]<target) l=mid+1;
            else r=mid-1;
        }
        return -1;
    }
};

436. Find Right Interval

Description:

Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the “right” of i.

For any interval i, you need to store the minimum interval j’s index, which means that the interval j has the minimum start point to build the “right” relationship for interval i. If the interval j doesn’t exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array.

Note:

  1. You may assume the interval’s end point is always bigger than its start point.
  2. You may assume none of these intervals have the same start point.

Example 1:

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

Output: [-1]

Explanation: There is only one interval in the collection, so it outputs -1.

Example 2:

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

Output: [-1, 0, 1]

Explanation: There is no satisfied "right" interval for [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point;
For [1,2], the interval [2,3] has minimum-"right" start point.

Example 3:

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

Output: [-1, 2, -1]

Explanation: There is no satisfied "right" interval for [1,4] and [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point.

解题思路：我们需要对区间排序，并且需要记录原有索引，所以使用map 数据结构；然后使用二分查找找到相应的区间，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct Interval {
    int start;
    int end;
    Interval() : start(0), end(0) {}
    Interval(int s, int e) : start(s), end(e) {}
 };
class Solution {
public:
    vector<int> findRightInterval(vector<Interval>& intervals) {
        
        vector<int> res;
        map<int, int> hash;
        for(int i=0;i<intervals.size();i++){
            hash[intervals[i].start]=i;
        }
        for(auto in : intervals){
            auto itr = hash.lower_bound(in.end);
            if(itr==hash.end()) res.push_back(-1);
            else res.push_back(itr->second);
        }
        return res;
    }
};

34. Search for a Range

Description:

Given an array of integers 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].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

解题思路：此题属于index search,数组中会出现多个相同的目标值，我们需要确定起始和终止的位置。这样的话，其实我们需要做两次BS，即从两个反方向进行，代码如下：

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
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> res(2,-1);
        if(nums.size()==0) return res;
        int l=0;
        int r=nums.size()-1;
        while(l<r){
            int mid = (l+r)/2;
            if(nums[mid]<target) l=mid+1;
            else r=mid;
        }
        
        if(nums[l]!=target) return res;
        else res[0]=l;
        
        r=nums.size()-1;
        while(l<r){
            int mid=(l+r)/2+1;
            if(nums[mid]>target) r=mid-1;
            else l=mid;
        }
        res[1]=r;
        return res;
    }
};

454. 4Sum II

Description:

Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l]is zero.

To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.

Example:

1
2
3
4
5
6
7
8
9
10
11
12
13
Input:
A = [ 1, 2]
B = [-2,-1]
C = [-1, 2]
D = [ 0, 2]

Output:
2

Explanation:
The two tuples are:
1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
        unordered_map<int,int> abHash;
        for(auto a : A){
            for(auto b : B){
                ++abHash[a+b];
            }
        }
        int count=0;
        for(auto c : C){
            for(auto d : D){
                auto itr = abHash.find(0-c-d);
                if(itr!=abHash.end()) count+= itr->second;
            }
        }
        return count;
    }
};

74. Search a 2D Matrix

Description: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.

For example,

Consider the following matrix:

1
2
3
4
5
6
[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

解题思路：将二维数组按照一维数组进行处理，属于index search, 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.size()==0||matrix[0].size()==0) return false;
        int row = matrix.size();
        int col = matrix[0].size();
        int l=0, r=row*col-1;
        while(l<r){
            int mid=(l+r)/2;
            if(matrix[mid/col][mid%col]<target) l=mid+1;
            else r=mid;
        }
        return matrix[l/col][l%col]==target;
    }
};

81. Search in Rotated Sorted Array II

Description:

Follow up for “Search in Rotated Sorted Array”:
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

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).

Write a function to determine if a given target is in the array.

The array may contain duplicates.

解题思路：旋转数组问题关键是找到最小值位置，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    bool search(vector<int>& nums, int target) {
        if(nums.size()==0) return false;
        int lo =0, hi = nums.size()-1;
        int mid = 0;
        while(lo<hi){
            mid=(lo+hi)/2;
            if(nums[mid]==target) return true;
            if(nums[mid]>nums[hi]){
                if(nums[mid]>target && nums[lo] <= target) hi = mid;
                else lo = mid + 1;
            }else if(nums[mid] < nums[hi]){
                if(nums[mid]<target && nums[hi] >= target) lo = mid + 1;
                else hi = mid;
            }else{
                hi--;
            }
        }
        return nums[lo] == target ? true : false;
    }
};

300. Longest Increasing Subsequence

Description:Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.

解题思路：动态规划，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int len = nums.size();
        if(len==0) return 0;
        vector<int> dp(len, 1);
        int res=1;
        for(int i=1; i<len; i++){
            for(int j=0; j<i; j++){
                if(nums[j]<nums[i]){
                    dp[i]=max(dp[i],dp[j]+1);
                }
            }
            res=max(res, dp[i]);
        }
        return res;
    }
};

718. Maximum Length of Repeated Subarray

Description:

Given two integer arrays A and B, return the maximum length of an subarray that appears in both arrays.

Example 1:

1
2
3
4
5
6
7
Input:
A: [1,2,3,2,1]
B: [3,2,1,4,7]
Output: 3
Explanation: 
The repeated subarray with maximum length is [3, 2, 1].

Note:

  1. 1 <= len(A), len(B) <= 1000
  2. 0 <= A[i], B[i] < 100

解题思路：动态规划，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int findLength(vector<int>& A, vector<int>& B) {
        int m=A.size(), n=B.size();
        if(!m || !n) return 0;
        int res = 0;
        vector<int> dp(n+1);
        for(int i=m-1; i>=0; i--){
            for(int j=0; j<n; j++){
                res = max(res, dp[j]=A[i]==B[j]?1+dp[j+1]:0);
            }
        }
        return res;
    }
};

153. Find Minimum in Rotated Sorted Array

Description:

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.

解题思路：旋转数组，代码如下：

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

230. Kth Smallest Element in a BST

Description:

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

**Note: **
You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

解题思路：本质就是计数，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
 
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        int count = treeCount(root->left);
        if(k<=count){
            return kthSmallest(root->left, k);
        }else if(k>count+1){
            return kthSmallest(root->right,k-1-count);
        }
        return root->val;
    }
    
    int treeCount(TreeNode* n){
        if(!n) return 0;
        return 1+treeCount(n->left)+treeCount(n->right);
    }
};

240. Search a 2D Matrix II

Description:

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 in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.

For example,

Consider the following matrix:

1
2
3
4
5
6
7
8
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.

Given target = 20, return false.

解题思路：经典题 ，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.size()==0||matrix[0].size()==0) return false;
        int rows = matrix.size();
        int cols = matrix[0].size()-1;
        int row = 0;
        while(cols>=0 && row < rows){
            if(matrix[row][cols]==target) return true;
            else if(matrix[row][cols]<target) row++;
            else cols--;
        }
        return false;
    }
};

378. Kth Smallest Element in a Sorted Matrix

Description:

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

1
2
3
4
5
6
7
8
9
matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13.

**Note: **
You may assume k is always valid, 1 ≤ k ≤ n2.

解题思路：本题很经典，此题属于range search，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int rows = matrix.size();
        int cols = matrix[0].size();
        int lo=matrix[0][0], hi=matrix[rows-1][cols-1]+1;
        while(lo<hi){
            int mid=lo+(hi-lo)/2;
            int count=0, j=cols-1;
            for(int i=0; i<rows; i++){
                while(j>=0 && matrix[i][j]>mid) j--;
                count+=(j+1);
            }
            if(count<k) lo=mid+1;
            else hi=mid;
        }
        return lo;
    }
};

658. Find K Closest Elements

Description:Given a sorted array, two integers k and x, find the k closest elements to x in the array. The result should also be sorted in ascending order. If there is a tie, the smaller elements are always preferred.

Example 1:

1
2
3
Input: [1,2,3,4,5], k=4, x=3
Output: [1,2,3,4]

Example 2:

1
2
3
Input: [1,2,3,4,5], k=4, x=-1
Output: [1,2,3,4]

Note:

  1. The value k is positive and will always be smaller than the length of the sorted array.
  2. Length of the given array is positive and will not exceed 104
  3. Absolute value of elements in the array and x will not exceed 104

UPDATE (2017/9/19):
The arr parameter had been changed to an array of integers (instead of a list of integers). Please reload the code definition to get the latest changes.

解题思路：先找到x（大于x的第一元素）在数组中的位置，然后在此位置周围找到k个元素，代码如下：

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
class Solution {
public:
    vector<int> findClosestElements(vector<int>& arr, int k, int x) {
        int len=arr.size();
        int index = low_bound(arr, len, x);
        int i=index-1, j=index;
        while(k--){
            i<0||(j<len && abs(arr[i]-x)>abs(arr[j]-x))?j++:i--;
        }
        return vector<int>(arr.begin()+i+1,arr.begin()+j);
    }
    
    int low_bound(vector<int> &nums, int len, int target){
        if(!len) return 0;
        if(nums[0]>=target) return 0;
        else if(nums[len-1]<target) return len-1;
        int lo=0, hi=len-1;
        while(lo<hi){
            int mid=lo+(hi-lo)/2;
            if(nums[mid]==target) return mid;
            if(nums[mid]<target) lo=mid+1;
            else hi=mid;
        }
        return lo;
    }
};

209. Minmum Size Subarray Sum

Description:

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

click to show more practice.

Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.

解题思路：双指针法，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int len = nums.size();
        if(len==0) return 0;
        int res=INT_MAX;
        int i=0,j=0,sum=0;
        while(j<len){
            sum+=nums[j++];
            while(sum>=s){
                res = min(res,j-i);
                sum-=nums[i++];
            }
        }
        return res==INT_MAX?0:res;
    }
};

287. Find the Duplicate Number

Description:

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

  1. You must not modify the array (assume the array is read only).
  2. You must use only constant, O(1) extra space.
  3. Your runtime complexity should be less than O(n2).
  4. There is only one duplicate number in the array, but it could be repeated more than once.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

解题思路：代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = nums[0];
        int fast = nums[nums[0]];
        while(slow!=fast){
            slow=nums[slow];
            fast=nums[nums[fast]];
        }
        fast=0;
        while(slow!=fast){
            slow=nums[slow];
            fast=nums[fast];
        }
        return slow;
    }
};

ciicA BOCer

个人简介