LC T668笔记 & 有关二分查找、第K小数、BFPRT算法

LC T668笔记 【涉及知识:二分查找、第K小数、BFPRT算法】

【以下内容仅为本人在做题学习中的所感所想,本人水平有限目前尚处学习阶段,如有错误及不妥之处还请各位大佬指正,请谅解,谢谢!】

 

!!!观前提醒!!!

【本文篇幅较大,如有兴趣建议分段阅读】

 

有关二分查找

作用:在有序集合中快速查找目标值

适用性:

  1. 只能查找有序的数据集

顺序存储的数据结果就是数组了,也就是二分查找只能从数组中查找,而不能查找链式存储的数据集,比如查找链表中的数,就不能用二分查找。

  2. 针对的是静态有序数据集

二分查找适合那种不经常变动的数据集合。如果经常插入、删除的数据集,每次插入和删除都要保证集合数据的有序,维护动态数据有序的成本很高。所以二分查找适合从有序的不经常变动的数据集合中查找。适合数据集合已经排好序,但是需要经常查找的场景。

  3. 不适合数据量太大或者太小的场景

因为二分查找需要依赖数组这种数据结构,而数组要求连续的内存空间,其需要把所有数据全部读入内存中,因此数据量太大的,对内存要求比较高。如果数据量只有几十个,那么不论是使用二分查找还是顺序遍历,查找效率都差不多。

 

有关二分查找的边界问题

“思路很简单,细节是魔鬼”

二分的几个常用情景:寻找一个数、寻找左侧边界、寻找右侧边界

以下是二分查找的基本框架:

 1 public int BinarySearch(int[] nums, int target) {  2     int left = 0, right = ...;   3     while(...) {  4         int mid = left + ((right - left) >> 1);  5         if (nums[mid] == target) {  6             ...  7         } else if (nums[mid] < target) {  8             left = ...  9         } else if (nums[mid] > target) { 10             right = ... 11         } 12     } 13     return ...; 14 }

分析二分查找的一个技巧是:不要出现 else,而是把所有情况用 else if 写清楚,这样可以清楚地展现所有细节。

(一)  寻找一个数

 1 public int BinarySearch(int[] nums, int target) {  2     int left = 0;   3     int right = nums.length - 1; //【1】  4   5     while(left <= right) { //【2】  6         int mid = left + ((right - left) >> 1);  7         if(nums[mid] == target)  8             return mid;   9         else if (nums[mid] < target) 10             left = mid + 1;  //【3】 11         else if (nums[mid] > target) 12             right = mid - 1;  //【4】 13     } 14     return -1; 15 }

  1. while中的循环条件

循环条件由搜索区间的结构确定,当找到目标值后,返回即可;

若没找到则需考虑终止情况。此处的搜索区间的结构是两端闭区间。当left == right时,表示区间[left, right],此时区间内仍有一个数值未被搜索,若此时结束循环,可能错过对目标值的匹配,因此需要继续查找,则终止条件应当是left > right时,此时搜索区间为空。所以此处while中应当为“<=”。

如果要使用小于号,则在结尾加一句判断即可。

1 return nums[left] == target ? left : -1;

  2.  left与right的加加减减

边界的加减也由搜索区间的结构确定。在[left, right]中mid被检测后,需要据mid将其划分为两个区间,若mid位置上的值不等于target,则不用再考虑mid。因为边界均可取到,所以搜索区间因改为[left, mid – 1]或[mid + 1, right]

  3.  缺点

当数据中重复出现目标元素,则返回的是在重复序列中中间位置的索引,并不能得到其左侧或右侧边界。如{1, 2, 2, 2, 3, 5},target = 2,此时返回索引为2,但其边界为[1, 3]

(二)  寻找左侧边界

 1 public int LeftBound(int[] nums, int target) {  2     if (nums.length == 0) return -1;  3     int left = 0;  4     int right = nums.length; //【1】  5       6     while (left < right) { //【2】  7         int mid = left + ((left + right) >> 1);  8         if (nums[mid] == target) {  9             right = mid; //【3】 10         } else if (nums[mid] < target) { 11             left = mid + 1; 12         } else if (nums[mid] > target) { 13             right = mid; //【4】 14         } 15     } 16     return left; 17 }

  1.  while中的循环条件

同理,此处的搜索区间为左闭右开型,当left == right时,表示区间[left, right),此时的区间已经为空,故可以终止。

注:这里解释一下为何上面用两端闭区间,而这里用左开后闭区间。因为这样的写法比较普遍,不这么写也可以,后文将会展示三种写法(两端闭,左开右闭,左闭右开)。

  2.  left与right的加减

因为此处是左闭右开区间,在[left, right)中mid被检测后,需要据mid将其划分为两个区间,[left, mid)和[mid + 1, right)。为了保证区间结构不变,所以right应变为mid,left应变为mid + 1

  3.  有关结尾的返回值

返回值表示目标值在序列中的左侧边界,等价于小于目标值的元素个数。分析可知left的取值范围是[0, nums.Length],所以当left == nums.Length时,说明没有一个元素小于target,即target在该序列中不存在,返回-1即可。(当然,最终的返回值也可以是right,因为终止条件是left == right)

1 if (left == nums.length) return -1; 2 return nums[left] == target ? left : -1;

  4.  该算法的核心,即为何可以查找左侧边界

1 if (nums[mid] == target)  2     right = mid;

当nums[mid] == target时,因为数据有序,说明mid左侧可能存在target,所以应缩小上界,不断向左收缩。

  5.  统一格式,将while循环加入等号

据原理,只需将right初值设为nums.Length – 1;right的变化改为mid – 1即可。

 1 public int LeftBound(int[] nums, int target) {  2     int left = 0, right = nums.length - 1;  3     while (left <= right) {  4         int mid = left + (right - left) / 2;  5         if (nums[mid] == target) {  6             right = mid - 1;  7             left = mid + 1;  8         } else if (nums[mid] > target) {  9             right = mid - 1; 10         } else if (nums[mid] < target) { 11             left = mid + 1; 12         } 13     } 14     if (left >= nums.length || nums[left] != target) 15         return -1; 16     return left; 17 }

(三)  寻找右边界

 1 public int RightBound(int[] nums, int target) {  2     if (nums.length == 0) return -1;  3     int left = 0, right = nums.length;  4     while (left < right) {  5         int mid = left + ((left + right) >> 1);  6         if (nums[mid] == target) {  7             left = mid + 1; //【1】  8         } else if (nums[mid] < target) {  9             left = mid + 1; 10         } else if (nums[mid] > target) { 11             right = mid; 12         } 13     } 14     return left - 1; //【2】 15 }

  1.  left与right的加减

因为此处是左闭右开区间,在[left, right)中mid被检测后,需要据mid将其划分为两个区间,[left, mid)和[mid + 1, right) 。为了保证区间结构不变,所以right应变为mid,left应变为mid + 1

  2.  有关最后返回值

因为对left的更新为mid + 1,结束时会产生以下结果:

 LC T668笔记 &amp; 有关二分查找、第K小数、BFPRT算法

[注:上图来源于搜索引擎查找结果】

所以需返回left – 1(也可返回right - 1)。

同理,当left == 0时,说明没有一个元素大于target,即target在该序列中不存在,返回-1即可。

1 if (left == 0) return -1; 2 return nums[left-1] == target ? (left-1) : -1;

  3.  统一格式

 1 public int RightBound(int[] nums, int target) {  2     int left = 0, right = nums.length - 1;  3     while (left <= right) {  4         int mid = left + ((right - left) >> 1);  5         if (nums[mid] == target) {  6             left = mid + 1;  7         } else if (nums[mid] > target) {  8             right = mid - 1;  9         } else if (nums[mid] < target) { 10             left = mid + 1; 11         } 12     } 13     if (right < 0 || nums[right] != target) 14         return -1; 15     return right; 16 }

 

小结

1. 写二分查找时,尽量不要出现 else,将所有情况列出来便于分析。

2. 注意搜索区间形式和 while 的终止条件,若存在漏掉的元素,最后特判。

3. 如需定义左闭右开的搜索区间,搜索左右边界,只要在 nums[mid] == target 时做修改即可,搜索右侧时需要减一

4. 如果将搜索区间全都统一成两端闭,只要修改 nums[mid] == target 条件处的代码和返回的逻辑即可。

 

从一维二分谈起

二分法,用于在集合中查找某些符合要求的元素,可以将时间复杂度降低至对数级。使用二分法的前提查找序列的有序性,主要思想是从序列中间位置开始,根据当前的中间值与目标值的大小关系,修改区间端点,确定目标值所在区间。

题意:在半有序的结合中查找目标元素的索引值

思想:选定中点,比较中点值来更改区间,但需要先判断当前所查找的区间是否为有序区间,否则不能使用二分法

 1 //C# Version  2   3 public class Solution {  4     public int Search(int[] nums, int target) {  5         int n = nums.Length;  6         if(n == 0) return -1;  7         if(n == 1) return nums[0] == target ? 0 : -1;  8           9         int left = 0, right = n - 1; 10         while(left <= right) { 11             int mid = left + ((right - left) >> 1); 12             if(target == nums[mid]) return mid; 13             if(nums[0] <= nums[mid]) { 14                 if(nums[0] <= target && target < nums[mid]) right = mid - 1; 15                 else left = mid + 1; 16             } 17             else if(nums[0] > nums[mid]){ 18                 if(nums[mid] < target && target <= nums[n - 1]) left = mid + 1; 19                 else right = mid - 1; 20             } 21         } 22         return -1; 23     } 24 }

 

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

 

题意:找出数组中满足其和大于等于目标值的长度最小的连续子序列

思想:要判断连续区间内的和,就先求出原数组的前缀和,因为题保证了数组中每个元素都为正,所以前缀和一定是递增的,保证了二分的正确性。

得到前缀和之后,对于每个开始下标 i,可通过二分查找得到大于或等于i的最小下标 bound,使得 sum[bound] - sum [i−1] ≥ target,并更新子数组的最小长度,此时子数组的长度是bound - i + 1。

 【注:此解法非最优解】

 1 //C# Version  2   3 public class Solution {  4     public int MinSubArrayLen(int target, int[] nums) {  5         int n = nums.Length;  6         if (n == 0) return 0;  7         int ans = int.MaxValue;  8         int[] sums = new int[n + 1];  9         for (int i = 1; i <= n; ++i)  10             sums[i] = sums[i - 1] + nums[i - 1]; 11         for (int i = 1; i <= n; ++i) { 12             int s = target + sums[i - 1]; 13             int bound = LowerBound(sums, i, n - 1, s); 14             if (bound != -1) 15                 ans = Math.Min(ans, bound - i + 1); 16         } 17         return ans == int.MaxValue ? 0 : ans; 18     } 19     private int LowerBound(int[] nums, int left, int right, int s) { 20         while (left <= right) { 21             int mid = left + ((right - left) >> 1); 22             if (nums[mid] < s) left = mid + 1; 23             else right = mid - 1; 24         }  25         return (nums[left] >= s) ? left : -1; 26     } 27 }

 

 1 //C++ Version  2   3 class Solution {  4 public:  5     int minSubArrayLen(int s, vector<int>& nums) {  6         int n = nums.size();  7         if (n == 0) return 0;  8         int ans = INT_MAX;  9         vector<int> sums(n + 1, 0);  10         for (int i = 1; i <= n; i++) 11             sums[i] = sums[i - 1] + nums[i - 1]; 12         for (int i = 1; i <= n; i++) { 13             int target = s + sums[i - 1]; 14             auto bound = lower_bound(sums.begin(), sums.end(), target); 15             if (bound != sums.end()) 16                 ans = min(ans, static_cast<int>((bound - sums.begin()) - (i - 1))); 17         } 18         return ans == INT_MAX ? 0 : ans; 19     } 20 };

 

题意:找到数组中某个峰值元素的索引(且nums[-1]与nums[len] = 负无穷)

思想:首先思考如何判断峰值所在区间。

假设mid < mid + 1

  • 对于mid – 1,无论是mid – 1 > mid还是mid – 1 > mid均不能得到mid是峰值;
  • 对于mid + 2,有两种情况:若mid + 2 < mid + 1则峰值为mid + 1;若mid + 2 > mid + 1,继续后推,由于边界后的值为-∞,那么一定可以得到最后一个值为峰值。

综上:峰值一定在较大的一部分。

 1 //C# Version  2   3 public class Solution {  4     public int FindPeakElement(int[] nums) {  5         int left = 0, right = nums.Length - 1;  6         while(left < right)  7         {  8             int mid = left + (right - left) / 2;  9             if(nums[mid] > nums[mid + 1]) right = mid; 10             else left = mid + 1; 11         } 12         return left; 13     } 14 }

 

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

 

小结

一维二分思想和操作较为简单,具体步骤为:

  1. 确定并构建查找对象。即是查找元素,还是查找和、差等,构建出用于查找的序列,如:前缀和。

  2.  判断二分后目标值可能的所在区间。一般是通过中值和目标值的比较更改区间,特殊地(如峰值寻找)需要运用一定数学知识进行判断。

 

有关二维二分

二维本质上可以看作是一维的叠加,某些简单的情况下,可以一维一维的查找。也可以从定义出发,从中点开始进行区间更改。当然,二维二分也有一些常见的变式,如从一个端点、对角线两个端点出发等。

题意:在二维矩阵中查找某个值是否存在。

思想:可以将二维数组划分为一维数组,一行一行或一列一列进行判断。可以对矩阵的第一列的元素二分查找,找到最后一个不大于目标值的元素,然后在该元素所在行,进行二分查找目标值是否存在。

 1 //C# Version  2   3 class Solution {  4     public bool SearchMatrix(int[][] matrix, int target) {  5         int rowIndex = BinarySearchFirstColumn(matrix, target);  6         if (rowIndex < 0) return false;  7         return BinarySearchRow(matrix[rowIndex], target);  8     }  9  10     private int BinarySearchFirstColumn(int[][] matrix, int target) { 11         int low = -1, high = matrix.Length - 1; 12         while (low < high) { 13             int mid = (high - low + 1) / 2 + low; 14             if (matrix[mid][0] <= target) low = mid; 15             else high = mid - 1; 16         } 17         return low; 18     } 19  20     private bool BinarySearchRow(int[] row, int target) { 21         int low = 0, high = row.Length - 1; 22         while (low <= high) { 23             int mid = (high - low) / 2 + low; 24             if (row[mid] == target) return true; 25             else if (row[mid] > target) high = mid - 1; 26             else low = mid + 1; 27         } 28         return false; 29     } 30 }

 

也可以从定义出发,从中间点开始进行判断。

 1 //C# Version  2   3 public class Solution {  4     public bool SearchMatrix(int[][] matrix, int target) {  5         int m = matrix.Length, n = matrix[0].Length;  6         int low = 0, high = m * n - 1;  7         while (low <= high) {  8             int mid = low + ((high - low) >> 1);  9             int x = matrix[mid / n][mid % n]; 10             if (x < target) low = mid + 1; 11             else if (x > target) high = mid - 1; 12             else return true; 13         } 14         return false; 15     } 16 }

 

注意到每行的第一个整数大于前一行的最后一个整数。因此,把每一行拼接到前一行可以得到一个递增序列,所以可以从右上角开始进行判断。

 1 //C# Version  2   3 public class Solution {  4     public bool SearchMatrix(int[][] matrix, int target) {  5         int n = matrix.Length;  6         if(n == 0) return false;  7         int row = 0, col = matrix[0].Length - 1;  8         while(row < n && col >= 0)  9         { 10             if(matrix[row][col] < target) row++; 11             else if(matrix[row][col] >target) col--; 12             else return true; 13         } 14         return false; 15     } 16 }

 

 1 //C++ Version  2   3 class Solution {  4 public:  5     bool searchMatrix(vector<vector<int>>& matrix, int target) {  6         int row = matrix.size(), col = matrix[0].size();  7         for(int i = 0, j = col-1; i < row && j >= 0;) {  8             if(matrix[i][j] == target)   9                 return true; 10             else if(matrix[i][j] > target)  11                 j--; 12             else if(matrix[i][j] < target) 13                 i++; 14         } 15         return false; 16     } 17 };

 

题意:在矩阵中找到第K小数

思想:可以从定义出发,从中间点开始进行判断。关键是统计对于当前数mid,有多少个比它小的数。

若每行的第一个整数大于前一行的最后一个整数,则cnt = i * n + j。但本题不满足该条件,则需要寻找一个参照值,通过循环,统计小于等于当前值的元素数。观察四个边角,左上角的元素最小,右下角的元素最大,而左下角和右上角的元素大小与mid相比是未定的,不妨取二者其一作为参照值。

在此,取左下角的值为参照值。

 1 //C# Version  2   3 public class Solution {  4     public int KthSmallest(int[][] matrix, int k) {  5         int n = matrix.Length;  6         int left = matrix[0][0], right = matrix[n - 1][n - 1];  7         while(left < right) {  8             int mid = left + ((right - left) >> 1);  9             if(Check(matrix, mid, k, n)) right = mid; 10             else left = mid + 1; 11         } 12         return left; 13     } 14     private bool Check(int[][] matrix, int mid, int k, int n) { 15         int cnt = 0; 16         int i = n - 1, j = 0; 17         while(i >= 0 && j < n) { 18             if(matrix[i][j] > mid) i--; 19             else { 20                 cnt += i + 1; 21                 j++; 22             } 23         } 24         return cnt >= k; 25     } 26 }

 

本题与上题类似,只是在计数上有变化。

 1 /C# Version  2   3 public class Solution {  4     public int FindKthNumber(int m, int n, int k) {  5         int left = 1, right = m * n;  6         while(left < right) {  7             int mid = left + ((right - left) >> 1);  8             if(CheckCnt(mid, k, m, n)) right = mid;  9             else left = mid + 1; 10         } 11         return left; 12     } 13     private bool CheckCnt(int mid, int k, int m, int n) { 14         int cnt = 0; 15         for(int i = 1; i <= m; i++) cnt += Math.Min(mid / i, n); 16         return cnt >= k; 17     } 18 }

 

小结

二维二分通常从边角出发,通常以边角值为参照值,进行区间的更新。其本质依旧是比大小,改区间。

 

有关第K小数

在此介绍一种算法:中位数的中位数算(BFPRT),该算法主要解决TOP-K问题。

有一个经典的问题,“从长度为N的无序数组中找出前k大的数”。TOP-K问题的最简单解法为快速排序后取第K大的数,但快速排序可能会达到最坏情况时间复杂度O(n2),且会对无用的数据进行排序操作(归并除外)。而该算法的主要优化是,修改快速排序选择主元的方法,优化最坏时间复杂度。

对于快速排序,一般选择中间位置的元素作为参照值,将小的数移到参照值左边,大的数移到右边,此时对于中间位置的该值,即为序列中第n/2小的数

那么,是否可以用类似的方法,通过一次O(n)的操作找出第k小数呢?

该算法通过“随机选择”实现了这个操作,其思想与快排类似,仅仅改变了对参照值的选取。

具体流程:

  1.将n个元素划为 n/5 组,每组5个,至多只有一组由 n%5 个元素组成。

  2.寻找每一个组的中位数(可以用插排)。

  3.对步骤2选出的 n/5 个中位数,重复步骤1和步骤2,递归下去,直到剩下一个数字。

  4.最终剩下的数字近似为序列的中位数pivot,把小于等于它的数放左边,大于的数放右边。

  5.判断pivot的位置与k的大小,如果pivot > k,则在[0, pivot – 1]内寻找第k小数;反之在[pivot + 1, n - 1]内寻找 k – pivot 小的数。

注意下面两种分治的思想:

  1.分治法O(nlogn):大问题分解为小问题,小问题都要递归各个分支,例如:快速排序。

  2.减治法O(n):大问题分解为小问题,小问题只要递归一个分支,例如:二分查找,随机选择。

 1 #include <bits/stdc++.h>  2 using namespace std;  3   4 int InsertSort(int array[], int left, int right);  5 int GetPivotIndex(int array[], int left, int right);  6 int Partition(int array[], int left, int right, int pivot_index);  7 int BFPRT(int array[], int left, int right, int k);  8   9 ///划分 10 int Partition(int arr[], int left, int right, int pivot_index) { 11     swap(arr[pivot_index], arr[right]); // 把主元放置于末尾 12  13     int partition_index = left; // 跟踪划分的分界线 14     for (int i = left; i < right; i++) 15         if (arr[i] < arr[right]) 16             swap(arr[partition_index++], arr[i]); // 比pivot小的都放在左侧 17  18     swap(arr[partition_index], arr[right]); // 最后把pivot换回来 19     return partition_index; 20 } 21  22 ///返回第 k 小数的下标 23 int BFPRT(int arr[], int left, int right, int k) { 24     int pivot_index = GetPivotIndex(arr, left, right); // 得到中位数的中位数下标 25     int partition_index = Partition(arr, left, right, pivot_index); // 进行划分,返回划分边界 26     int num = partition_index - left + 1; 27  28     if (num == k) 29         return partition_index; 30     else if (num > k) 31         return BFPRT(arr, left, partition_index - 1, k); 32     else 33         return BFPRT(arr, partition_index + 1, right, k - num); 34 } 35  36 ///返回 [left, right]的中位数。 37 int Insertion(int arr[], int left, int right) { 38     int temp, j; 39     for (int i = left + 1; i <= right; i++) { 40         temp = arr[i]; 41         j = i - 1; 42         while (j >= left && arr[j] > temp) { 43             arr[j + 1] = arr[j]; 44             j--; 45         } 46         arr[j + 1] = temp; 47     } 48     return left + ((right - left) >> 1); 49 } 50  51 ///数组每五个元素作为一组,并计算每组的中位数,最后返回这些中位数的中位数下标 52 ///末尾返回语句最后一个参数多加 1 的作用是向上取整,可以始终保持 k 大于 0。 53 int GetPivotIndex(int arr[], int left, int right) { 54     if (right - left < 5) 55         return Insertion(arr, left, right); 56     int sub_right = left - 1; 57      58     // 每五个作为一组,求出中位数,并把这些中位数全部依次移动到数组左边 59     for (int i = left; i + 4 <= right; i += 5) { 60         int index = Insertion(arr, i, i + 4); 61         swap(arr[++sub_right], arr[index]); 62     } 63  64     // 利用 BFPRT 得到这些中位数的中位数下标 65     return BFPRT(arr, left, sub_right, ((sub_right - left + 1) >> 1) + 1); 66 } 67  68 int main() { 69     ios::sync_with_stdio(false); 70     int k = 8; // 1 <= k <= array.size 71     int nums[20] = { 12, 9, 7, 1, 13, 9, 15, 0, 26, 2, 17, 5, 14, 31, 6, 18, 22, 7, 19, 41 }; 72  73     cout << "The Source Data:"; 74     for (int i = 0; i < 20; i++) 75         cout << nums[i] << " "; 76     cout << endl; 77  78     // 因为是以 k 为划分,所以还可以求出第 k 小值 79     cout << "The Kth smallest number:" << nums[BFPRT(nums, 0, 19, k)] << endl; 80  81     cout << "After Processing:"; 82     for (int i = 0; i < 20; i++) 83         cout << nums[i] << " "; 84     cout << endl; 85     return 0; 86 }

LC T668笔记 &amp; 有关二分查找、第K小数、BFPRT算法

 

Enable collaborative features and customize widget: Bing Webmaster Portal

举报
发表评论

相关文章

探索-发展-风口-前沿
最近文章
  • 聊聊程序员的信仰
  • 机器学习基础总结
  • C#实现聊天消息渲染、图文混排(支持Windows、Linux)
  • Performance API不完全使用指北
  • 计算机重装Windows操作系统
  • .NET周报 【2月第1期 2023-02-04】
  • 当前内容话题
  • 0