剑指offer68-77二分查找、排序

二分查找系列

剑指 Offer II 068. 查找插入位置

给定一个排序的整数数组 nums 和一个整数目标值 target ，请在数组中找到 target ，并返回其下标。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

输入: nums = [1,3,5,6], target = 5
输出: 2

找目标的下标，找不到输出应该插入的下标

mid = left + ((right - left) >> 1) 的写法比 mid = (left + right) / 2 好，因为 left + right 可能会溢出，同时位运算的效率更高； >> 1 作用相当于除二，这个看leetcode汇总

当出现 nums[mid] >= target 的情况，还需要加一个判断 mid == 0 || nums[mid - 1] < target，若成立则说明，前一个数比 target 小，那么就找到了位置。若在 while 循环内都未找到符合要求的位置，那么说明 target 比所有的数都要大，需要插入到数组的最后一个数字之后，即返回 nums.size()。

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

剑指 Offer II 069. 山峰数组的顶部

arr.length >= 3
存在 i（0 < i < arr.length - 1）使得：
arr[0] < arr[1] < … arr[i-1] < arr[i]
arr[i] > arr[i+1] > … > arr[arr.length - 1]
给定由整数组成的山峰数组 arr ，返回任何满足 arr[0] < arr[1] < … arr[i - 1] < arr[i] > arr[i + 1] > … > arr[arr.length - 1] 的下标 i ，即山峰顶部。

输入：arr = [3,4,5,1]
输出：2

左右都比它小，位置>0，题目保证是山峰数组，这里只需要返回在数组里的位置

方法二分查找

使用二分查找时，题目中已经明确山峰不在数组的首尾，所以可以把 left 和 right 初始化为 1 和 arr.size() - 2。

代码

class Solution {
public:
    int peakIndexInMountainArray(vector<int>& arr) {
        int left = 1;
        int right = arr.size() - 2;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);//mid = (left + right) / 2
            if (arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1]) {
                return mid;
            }
            arr[mid] > arr[mid - 1] ? left = mid + 1 : right = mid - 1;
        }
        return -1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

剑指 Offer II 070. 排序数组中只出现一次的数字

给定一个只包含整数的有序数组 nums ，每个元素都会出现两次，唯有一个数只会出现一次，请找出这个唯一的数字。

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2

如果是要求O（n）的话，可以直接异或，因为最后只剩0和一个单独的数异或，比如000异或100=100

方法一：根据对不相等进行二分查找

下面保留疑问，如果不相等，为什么能直接让right=mid-1，万一在mid和i之间呢，本身是与i做的比较，应该让right=i-1才对吧，但是这样通不过，原先那样可以通过

代码

原先的代码可以通过

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        int left = 0;
        int right = nums.size() / 2 - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1); //
            int i = 2 * mid;
            if (nums[i] != nums[i + 1]) {
                if (i == 0 || nums[i - 1] == nums[i - 2]) {
                    return nums[i];
                }
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        return nums.back();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

方法二：也根据成对进行二分查找

对于目标x，因为前面都是成对的，因此mid如果是偶数就应该和前面相比较，如果mid是奇数就应该和后面作比较，但是由于数组是从0开的的，因此正好反过来 应该mid是偶数就应该和后面作比较，是奇数就应该和前面作比较。在指针移动时，如果相等还好说明在后面，就应该left=mid+1，但如果不等于，就可能当前元素就是，那么right就应该=mid而不是mid-1

在判断mid是否是奇偶时，由于

因此不用判断奇偶了，直接比较

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

方法三 偶数下标的二分查找

成对出现且数组从0开始，因此目标下标一定是偶数，那么目标左侧的偶数下标与其右边一定都是相等的，目标右侧的偶数下标和其右侧一定是不同的。
因此只看偶数就可以了，在求mid时，如果是偶数，那就是当前值，如果是奇数需要-1，但是有个特点

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

4、普通方法

class Solution {
public:
    int singleNonDuplicate(vector<int>& nums) {
        /*
            如果当前 
             1 1 2 2 3 4 4 5 5
             0 1 2 3 4 5 6 7 8
             
             right = mid;

        */
        if(nums.size() == 0) return 0;
        int left  = 0;
        int right = nums.size() - 1;
        while(left < right){
          int  mid = left + (right - left)/2;
          cout << "left  : " << left << "   right" <<right <<"    mid" <<mid <<endl;
            int midd = mid % 2;
            if(midd == 0) //说明是偶数
            {
                if(nums[mid] == nums[mid + 1]) //如果两者相等，说明是后面
                  left =  mid + 1;
                else //如果 两者不相等 说明在前面
                  right = mid ;
            }
            else //说明是奇数
            {  //奇书应该与后面作比较
                if(nums[mid] == nums[mid - 1]) //如果两者相等，说明是后面
                  left =  mid + 1;
                else //如果 两者不相等 说明在前面
                  right = mid ;
            }    
        }
        return nums[left]; //返回right也对
    }
};
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

剑指 Offer II 071. 按权重生成随机数

输入：
inputs = [“Solution”,“pickIndex”]
inputs = [[[1]],[]]
输出：
[null,0]
解释：
Solution solution = new Solution([1]);
solution.pickIndex(); // 返回 0，因为数组中只有一个元素，所以唯一的选择是返回下标 0。

游戏开发中经常会碰到这样的需求：从一系列道具中随机抽出一个发给玩家，由于道具的价值不一样，所以抽取的概率并不是平均的。后台会处理成高价值的东西很难得到，要实现这种效果，需要给每个道具指定一个权重。比如道具A的权重是99，道具B的权重是1，那么99%的概率会抽到道具A，这就是基于权重的随机算法。

A=[3,5,4],W=[1,2,7]
3的权重为1/(1+2+7)=10%
5的权重为2/(1+2+7)=20%
那么100次选中3的次数可能是10次
选中5的概率是20次

本题没有A数组，仅有W数组，也就是看W下标的概率，比如上面的3就变成了下标0的概率是10%

方法：前缀和+二分查找

对于[1,3,5,4,2]的权重，新建一个数组，内容是前面加起来，就如上图一样生成的数组，那么等概率在[1, vector.back()] 生成数，然后再二分查找这个数在vector里的下标

class Solution {
public:
    vector<int> acc;
public:
    Solution(vector<int>& w) {
        acc.resize(w.size(), 0);
        int sum = 0;
        for (int i = 0; i < w.size(); ++i) {
            sum += w[i];
            acc[i] = sum;
        }
    }

    int pickIndex() {
        int rad = rand() % acc.back() + 1;
        int left = 0;
        int right = acc.size() - 1;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (rad <= acc[mid]) {
                if (mid == 0 || rad > acc[mid - 1]) {
                    return mid;
                }
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        return -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
29
30
31
32

剑指 Offer II 072. 求平方根

给定一个非负整数 x ，计算并返回 x 的平方根，即实现 int sqrt(int x) 函数。

正数的平方根有两个，只输出其中的正数平方根。

如果平方根不是整数，输出只保留整数的部分，小数部分将被舍去。

输入: x = 8
输出: 2
解释: 8 的平方根是 2.82842…，由于小数部分将被舍去，所以返回 2

方法 二分查找找k^2<=x

class Solution {
public:
    int mySqrt(int x) {
        int l = 0, r = x, ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if ((long long)mid * mid <= x) {
                ans = mid;
                l = mid + 1;
            }
            else {
                r = mid - 1;
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

剑指 Offer II 073. 狒狒吃香蕉

输入：piles = [30,11,23,4,20], h = 6
输出：23

一小时只能减x，如果能减没，一小时内就不动了，如果减不没下一个小时再减，以上面的输入为例，一小时减23个，30需要两次，11一次，23一次，4一次，20一次，所以需要2+1+1+1+1=6次，而这也是h=6需要的

方法 二分查找尝试

一小时最小是1，最大是数组里最大的元素
也就是在[1,max]里最小且能满足在规定时间内吃完

代码

class Solution {
private:
    // 返回狒狒速度 k 时需要吃完香蕉的时间[3,6,7,10] 
    int countTime(vector<int>& piles, int k) {
        int t = 0;
        for (auto& p : piles) {
            // t += (p - 1) / k + 1;
            t += p / k;
            t += ((p % k) > 0);
        }
        return t;
    }

public:
    int minEatingSpeed(vector<int>& piles, int h) {
        int left = 1;
        int right = *max_element(piles.begin(), piles.end());
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (countTime(piles, mid) <= h) {
                if (mid == 1 || countTime(piles, mid - 1) > h) {
                    return mid;
                }

                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        return -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
29
30
31
32
33

剑指 Offer II 074. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

合并分区，重复的进行合并

代码

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        if (intervals.size() == 0) {
            return {};
        }
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> merged;
        for (int i = 0; i < intervals.size(); ++i) {
            int L = intervals[i][0], R = intervals[i][1];
            if (!merged.size() || merged.back()[1] < L) {
                merged.push_back({ L, R });
            }
            else {
                merged.back()[1] = max(merged.back()[1], R);
            }
        }
        return merged;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

剑指 Offer II 075. 数组相对排序

给定两个数组，arr1 和 arr2，

arr2 中的元素各不相同
arr2 中的每个元素都出现在 arr1 中
对 arr1 中的元素进行排序，使 arr1 中项的相对顺序和 arr2 中的相对顺序相同。未在 arr2 中出现过的元素需要按照升序放在 arr1 的末尾。

输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
输出：[2,2,2,1,4,3,3,9,6,7,19]

代码

将arr2放到哈希表里，先出现的元素是小的

然后重新定义比较函数，具体看下面的注解

class Solution {
public:
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        unordered_map<int, int> rank;
        for (int i = 0; i < arr2.size(); ++i) {
            rank[arr2[i]] = i;
        }
        sort(arr1.begin(), arr1.end(), [&](int x, int y) {
            if (rank.count(x)) {
                return rank.count(y) ? rank[x] < rank[y] : true;
                /*在哈希表里的会小一点
                * 如果一个在哈希表里一个不在哈希表里，那么在哈希表里的大
                *    传递了两个元素，第一个元素在哈希表，第二个元素不在哈希表，那么第二个元素大
                *    传递两个元素，是想判断这两个哪个大，很显然第二个大，那么就返回true
                * 如果两个都在哈希表里，那么比较哈希表键对应的值
                *    两个元素，如果第一个大即rank[x] > rank[y]，那么返回false
                *              如果第二个大，那么返回true
                */
                }
            else {
                return rank.count(y) ? false : x < y;
                /* 如果第一个不在哈希表里，那么看第二个是否在哈希表里
                * 如果第二个不在哈希表里，那就是看这两个谁大了
                * 如果第二在哈希表里，由于在哈希表里的小，那么就返回false
                
                */
            }
            });
        return arr1;
    }
};
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

剑指 Offer II 076. 数组中的第 k 大的数字

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

方法一：基于快速排序的选择方法

可以先排序然后再找到第k个大的元素，但如果这样就没有利用上第k个最大元素的条件了。看本题先看快速排序在基本算法整理那里，
与快速排序差不多的是都有两个指针，这个看基本算法整理的快速排序2

如果函数返回的中间值位置刚好为 k - 1，那么数组 k - 1位置的数字就是第 k 大的数字。如果函数返回的位置大于 k - 1，那么第 k 的数字一定在当前中间值的左侧，于是对左侧区间进行分区。反之，则对右侧区间进行分区。

代码

class Solution {
private:
    int partition(vector<int>& nums, int start, int end) {
        int rad = rand() % (end - start + 1) + start;
        swap(nums[rad], nums[end]);
        int big = start - 1;
        for (int i = start; i < end; ++i) {
            if (nums[i] > nums[end]) {
                big++;
                swap(nums[big], nums[i]);
            }
        }
        big++;
        swap(nums[big], nums[end]);
        return big;
    }

public:
    int findKthLargest(vector<int>& nums, int k) {
        int start = 0;
        int end = nums.size() - 1;
        int i = partition(nums, start, end);
        while (i != k - 1) {
            i < k - 1 ? start = i + 1 :  end = i - 1;
            i = partition(nums, start, end);
        }
        return nums[k - 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
29

方法二：最小堆获得前k大

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> heap;
        for (int i = 0; i < nums.size(); ++i) {
            if (i < k) {
                heap.push(nums[i]);
            }
            else if (nums[i] > heap.top()) {
                heap.pop();
                heap.push(nums[i]);
            }
        }
        return heap.top();
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

剑指 Offer II 077. 链表排序

给定链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。