【刷题笔记】牛客网面试101必刷题刷题笔记(2)二分查找/排序部分_二分排序题

本文主要介绍的是牛客网面试必刷101里的二分查找/排序的所有题目的解析和答案，题号从BM17-BM22，希望给正在刷题的大家带来一些思路和灵感。

---

BM17 二分查找-1

描述

请实现无重复数字的升序数组的二分查找

给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标（下标从 0 开始），否则返回 -1

数据范围：0≤len(nums)≤2×10⁵， 数组中任意值满足 ∣val∣≤10⁹

进阶：时间复杂度 O(log⁡n)，空间复杂度 O(1)

思路：

1. 暴力解法：从前往后遍历数组，如果找到 $target$, 我们直接返回它的下标，如果遍历到最后还没有找到就直接返回-1。时间复杂度$O(N)$，空间复杂度$O(1)$
2. 分治思想：既然是排序好的数组，我们可以通过其有序性来排除一些值，比如找到中点，然后判断数组中点和$target$的值的大小关系。这样如果没有直接找到，我们每次就可以排除一半数量的值，时间复杂度变为$O(LogN)$.

我采用二分解法：

class Solution {
public:
    int binary_search(vector<int>& nums, int begin, int end, int tar)
    {
        //递归终止条件
        if(begin > end) return -1;
        int mid = (begin + end) >> 1;
      	//分区间： [begin, mid - 1] mid [mid + 1, end]
        if(nums[mid] < tar) return binary_search(nums, mid + 1, end, tar);
        else if(nums[mid] == tar) return mid;
        else return binary_search(nums, begin, mid - 1, tar);
    }
    int search(vector<int>& nums, int target) {
        // write code here
        int n = nums.size();
        return binary_search(nums, 0, n - 1, target);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

BM18 二维数组中的查找

描述

在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

[ [1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15] ]

给定 target = 7，返回 true。

给定 target = 3，返回 false。

数据范围：矩阵的长宽满足 0≤n,m≤500 ， 矩阵中的值满足 0≤val≤10⁹

进阶：空间复杂度 O(1) ，时间复杂度 O(n+m)

思路：

1. 暴力解法：暴力从左到右从上到下进行搜索。时间复杂度$O(MN)$.

2. 二分搜索：因为数组从左到右有序，从上到下有序，我们可以对每行进行二分搜索，时间复杂度为$O(MlogN)$.

   class Solution {
     public:
       int binary_search(vector<int>& nums, int begin, int end, int tar) {
           //递归终止条件
           if (begin > end) return -1;
           int mid = (begin + end) >> 1;
           if (nums[mid] < tar) return binary_search(nums, mid + 1, end, tar);
           else if (nums[mid] == tar) return mid;
           else return binary_search(nums, begin, mid - 1, tar);
       }
       bool Find(int target, vector<vector<int> >& array) {
           int m = array.size();//确定矩阵长度
           int n = array[0].size();//确定矩阵宽度
           for(int i = 0; i < m; ++i) //对每行二分查找，找到target，找到直接返回
           {
               int ret = binary_search(array[i], 0, n - 1, target);
               if(ret != -1) return true;
           }
           return false;
       }
   };
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19
   20
   21

3. 利用行和列都有序的特性进行线性搜索：

   我们虽然使用二分搜索对暴力做法进行了优化，但是，我们只是使用了行的有序特性，而没有使用列的有序特性。这也导致了我们的时间复杂度并不太优越。我们可以根据行和列都有序推出：

   行：左边的数都比右边小。

   列：下边的数都比上边大。

   所以我们选一个矩阵的中间点，判断和$target$之间的关系，如果相等返回，如果大于，需要变小，往左；如果小于，需要变大，往下。直至越界。

   注意，我们如果遍历，这个点只会往左，往下移动，所以可以初始化$ x = m - 1, y = 0$,判断越界的条件可以设置$ x >= 0, y < n $

   class Solution {
   public:
       bool Find(int target, vector<vector<int> >& array) {
           // write code here
           int m = array.size();//行数
           int n = array[0].size();//列数
           for(int x = 0, y = n - 1; x < m && y >=0;)
           {
               if(array[x][y] == target) return true;
               else if(array[x][y] < target) x++;
               else y--;
           }
           return false;
       }
   };
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15

   时间复杂度：因为是线性遍历，最多从左走到右，从下走到上，所以是$O(M+N)$，空间$O(1)$

4. 双二分查找：既然可以每行进行二分查找，就可以进行二维的双二分查找，每次比较矩阵中点值和target 的大小关系。

   因为矩阵中点值左边和上边（以矩阵中点为右下角的整个矩阵）都小于等于这个矩阵中点值，如果判断这个值小于$target$值，我们可以直接找右下区间的，以矩阵中点为左上角的矩阵都大于等于这个矩阵中点值，所以可以一下排除$1/4$ 的值。

   排除意味着，我们需要继续比对剩下的三块区间。

   class Solution {
   public:
       bool binary_search(int target, int left, int right, int up, int down, vector<vector<int> >& array)
       {
           if(left == right || up == down) return false;
           int midx = (left + right) >> 1;
           int midy = (up + down) >> 1;
           int midVal = array[midx][midy];
           if(midVal == target) return true;
           else if(midVal < target)
           {
               if(binary_search(target, midx + 1, right, up, down, array)) return true;
               if(binary_search(target, left, midx + 1, midy + 1, down, array)) return true;
           }
           else
           {
               if(binary_search(target, left, right, up, midy, array)) return true;
               if(binary_search(target, left, midx, midy, down, array)) return true;
           }
           return false;
       }
       bool Find(int target, vector<vector<int> >& array) {
           int m = array.size();//行数
           int n = array[0].size();//列数
           return binary_search(target, 0, m, 0, n, array);
       }
   };
   
   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

   ---

   BM19 寻找山峰

   描述

   给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。

   1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于

   2.假设 nums[-1] = nums[n] = −∞

   3.对于所有有效的 i 都有 nums[i] != nums[i + 1]

   4.你可以使用O(logN)的时间复杂度实现此问题吗？

   数据范围：

   1≤nums.length≤2×10⁵

   −2³¹<=nums[i]<=2³¹−1

   如输入[2,4,1,2,7,8,4]时，会形成两个山峰，一个是索引为1，峰值为4的山峰，另一个是索引为5，峰值为8的山峰。

思路：因为数组的最左边和最右边都是负无穷，所以最左边的是在递增，最右边是在递减，也就是肯定会存在一个峰值。我们随便选一个点，如果这个点大于下一个点，那么要么这个点就是拐点（峰值），要么拐点就在这个点的左侧。而右边不一定含有峰值（可以一直下降），所以我们这个题就变成了，如果找到一点i，arr[i] > arr[i + 1]，那么我们去左区间找峰值（含点i）对应操作是双指针left 和right 里的right 变成mid （因为含i 点）。否则就有可能：从左到i 点一直递增，这种情况下左区间没有峰值，但右边有峰值 或者是：从左到i 点有峰值，但是因为i 到i + 1 的位置也在递增，所以右侧一定也有峰值。综合考虑，我们知道右侧必定存在峰值，我们就可以去右边区间找峰值。left = mid + 1;

题目就变成了找到区间内递减区间的左端点，条件就是递减$（arr[i]>arr[i-1])$

class Solution {
  public:
    int findPeakElement(vector<int>& nums) {
        int n = nums.size();
        //找区间的左端点
        int left = 0;
        int right = n - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < nums[mid + 1]) left = mid + 1; //越过mid
            else right = mid; //包含mid
        }
        return left;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

---

BM20 数组中的逆序对

描述

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007

数据范围： 对于 50%的数据, size≤10⁴
对于100% 的数据, size≤10⁵

数组中所有数字的值满足 0≤val≤10⁹

要求：空间复杂度 O(n)，时间复杂度 O(nlogn)

输入描述：

题目保证输入的数组中没有的相同的数字

思路：

本题分类在二分查找/排序中，但实际上是一道归并的题目。我们面对这种逆序和题目，可以采取

1. 暴力解法：两个for 循环就可以搞定。但是时间复杂度O(N²)

2. 我们可以对暴力解法做优化：我们可以针对整个数组的左半区间找逆序对，再针对右半区间找逆序对，然后再在左区间中取一个数，右区间中取一个数（一左一右）找逆序对。关键点就是这个一左一右中取逆序对，如果我们实现左区间有序，右区间也有序，那么一左一右取逆序对的这个问题就可以大大简化：因为倘若左区间的一点下标$left$，右区间的一点下标$right$，有$nums[left]>nums[right]$,那么根据有序性，可以推出来 $left$右边的所有左半区间的点都大于这个$ nums[right]$，也就是说，这个逆序和数可以直接加上这段长度而不用再一个一个遍历，直接让$right++$，去判断 $nums[right]$ 变大之后，左边还大不大于右边？如果大于，我们继续加上这段区间的长度，如果不大于，就是左边的值小了，让左边的点向右移动就可以了。

   我们可以发现，这个思路实际上于归并排序的思路一样：取中间点，分别对左区间和右区间做递归调用（保证左右区间有序），双指针判断填入$tmp$数组，最后填入原数组中。

   我们只是在这个归并排序的基础上，加入一步，如果符合一定条件，我们让额外的一个int 加上一个数即可。

   class Solution {
   public:
       vector<int> tmp;
       void mergeSort(vector<int>& nums, int left, int right, int& ret)
       {
           if(left >= right) return;
           //取中
           int mid = (left + right) >> 1;
           //递归
           mergeSort(nums, left, mid, ret);
           mergeSort(nums, mid + 1, right, ret);
           //合并
           int cur1 = left, cur2 = mid + 1, i = 0;
           while(cur1 <= mid && cur2 <= right)
           {
               if(nums[cur1] <= nums[cur2]) tmp[i++] = nums[cur1++];
               else
               {
                   ret += mid - cur1 + 1;
                   ret %= (1000000007);
                   tmp[i++] = nums[cur2++];
               } 
           }
         	//处理未完成的区间
           while(cur1 <= mid) tmp[i++] = nums[cur1++];
           while(cur2 <= right) tmp[i++] = nums[cur2++];
   				//回填
         	for(int i = left; i <= right; ++i)
           {
               nums[i] = tmp[i - left];
           }
       }
       int InversePairs(vector<int>& nums) {
           int n = nums.size();
           int ret = 0;
           tmp.resize(n);
           mergeSort(nums, 0, n - 1, ret);
           return ret;
       }
   };
   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
   38
   39
   40

---

BM21 旋转数组的最小数字

描述

有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。

数据范围：1≤n≤10000，数组中任意元素的值: 0≤val≤10000

要求：空间复杂度：O(1)，时间复杂度：O(logn)

思路：

1. 暴力解法，直接遍历数组就可以求最小值，时间复杂度$O(N)$

2. 优化：举个例子：[3, 4, 5, 1, 2] 可以看到数组是先递增 -> 最小值 ->递增

   我们可以看出：旋转数组会有两段性：递增 -> 减 -> 递增，减的地方就是我们的最小值，而且根据原数组的递增性质，我们可以知道从减的地方开始(设为i），每个值都小于nums[0]，因为 i 位置 一直到 n - 1 位置，都是增的 而且衔接到现在的 0 位置。所以我们就把问题变成了寻找区间左端点的二分查找问题。

   但是本题目和leetcode 153 题不同的是，本题目是非减，而不是递增的数组，这就使得可以出现$[0,1,1,1,1,1,1,1]$这样的数组。我们原来的思路就不成立了。

   我们可以：分三个区间 $[left,mid][mid+1,right]$，我们称之为左区间和右区间。

   • 比较$nums[mid]>nums[right]$，成立的话说明 mid 落在左区间中，让 $left=mid+1$
   • 比较$nums[mid]<nums[right]$，成立的话说明 mid 落在右区间里，让 $right = mid $
   • 如果相等，我们并不知道在左边还是在右边，可以让$right--$ 以缩小范围。

   class Solution {
   public:
       int minNumberInRotateArray(vector<int>& nums) {
           int n = nums.size();
           int left = 0, right = n - 1;
           while(left < right)
           {
               int mid = left + (right - left) / 2;
               if(nums[mid] > nums[right])
               {
                   //排除这个区间
                   left = mid + 1;
               }
               else if(nums[mid] == nums[right]) right--;
               else right = mid;
           }
           return nums[left];
       }
   };
   1
   2
   3
   4
   5
   6
   7
   8
   9
   10
   11
   12
   13
   14
   15
   16
   17
   18
   19

---

BM22 比较版本号

描述

牛客项目发布项目版本时会有版本号，比如1.02.11，2.14.4等等

现在给你2个版本号version1和version2，请你比较他们的大小

版本号是由修订号组成，修订号与修订号之间由一个"."连接。1个修订号可能有多位数字组成，修订号可能包含前导0，且是合法的。例如，1.02.11，0.1，0.2都是合法的版本号

每个版本号至少包含1个修订号。

修订号从左到右编号，下标从0开始，最左边的修订号下标为0，下一个修订号下标为1，以此类推。

比较规则：

一. 比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较忽略任何前导零后的整数值。比如"0.1"和"0.01"的版本号是相等的

二. 如果版本号没有指定某个下标处的修订号，则该修订号视为0。例如，“1.1"的版本号小于"1.1.1”。因为"1.1"的版本号相当于"1.1.0"，第3位修订号的下标为0，小于1

三. version1 > version2 返回1，如果 version1 < version2 返回-1，不然返回0.

数据范围：

1<=version1.length,version2.length<=1000

version1 和 version2 的修订号不会超过int的表达范围，即不超过 32 位整数 的范围

进阶： 空间复杂度 O(1) ， 时间复杂度 O(n)

观察这个题目描述，非常的繁杂，但是实际上一切这种题目要求冗长的题，都是“paper tiger” （出自张宇）

其实读完题之后，就会发现，实际上就是使用双指针法，把字符串转换成int 来进行比较，点和点之间的比较一次，如果相等，就继续比较，直到二者都比较完即可。

class Solution {
public:
    int compare(string version1, string version2) {
				//定义双指针
      	int cur1 = 0, cur2 = 0;
        int n1 = version1.size(), n2 = version2.size();
        while(cur1 < n1 || cur2 < n2)
        {
          	//把字符串转换成num1, num2
            int num1 = 0, num2 = 0;
          	// 加上 cur1 < n1 防止while的越界
            while(cur1 < n1 && version1[cur1] != '.') num1 = num1 * 10 + (version1[cur1++] - '0');
            while(cur2 < n2 && version2[cur2] != '.') num2 = num2 * 10 + (version2[cur2++] - '0');
						
            if(num1 < num2) return -1;
            else if(num1 > num2) return 1;
            else {cur1++; cur2++; continue;}
        }
        return 0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21