赞
踩
本文主要介绍的是牛客网面试必刷101里的二分查找/排序的所有题目的解析和答案,题号从BM17-BM22,希望给正在刷题的大家带来一些思路和灵感。
描述
请实现无重复数字的升序数组的二分查找
给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标(下标从 0 开始),否则返回 -1
数据范围:0≤len(nums)≤2×105, 数组中任意值满足 ∣val∣≤109
进阶:时间复杂度 O(logn),空间复杂度 O(1)
思路:
我采用二分解法:
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); } };
描述
在一个二维数组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≤109
进阶:空间复杂度 O(1) ,时间复杂度 O(n+m)
思路:
暴力解法:暴力从左到右从上到下进行搜索。时间复杂度 O ( M N ) O(MN) O(MN).
二分搜索:因为数组从左到右有序,从上到下有序,我们可以对每行进行二分搜索,时间复杂度为 O ( M l o g N ) O(MlogN) 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; } };
利用行和列都有序的特性进行线性搜索:
我们虽然使用二分搜索对暴力做法进行了优化,但是,我们只是使用了行的有序特性,而没有使用列的有序特性。这也导致了我们的时间复杂度并不太优越。我们可以根据行和列都有序推出:
行:左边的数都比右边小。
列:下边的数都比上边大。
所以我们选一个矩阵的中间点,判断和 t a r g e t target 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;
}
};
时间复杂度:因为是线性遍历,最多从左走到右,从下走到上,所以是 O ( M + N ) O(M+N) O(M+N),空间 O ( 1 ) O(1) O(1)
双二分查找:既然可以每行进行二分查找,就可以进行二维的双二分查找,每次比较矩阵中点值和target 的大小关系。
因为矩阵中点值左边和上边(以矩阵中点为右下角的整个矩阵)都小于等于这个矩阵中点值,如果判断这个值小于 t a r g e t target target值,我们可以直接找右下区间的,以矩阵中点为左上角的矩阵都大于等于这个矩阵中点值,所以可以一下排除 1 / 4 1/4 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); } };
描述
给定一个长度为n的数组nums,请你找到峰值并返回其索引。数组可能包含多个峰值,在这种情况下,返回任何一个所在位置即可。
1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
2.假设 nums[-1] = nums[n] = −∞
3.对于所有有效的 i 都有 nums[i] != nums[i + 1]
4.你可以使用O(logN)的时间复杂度实现此问题吗?
数据范围:
1≤nums.length≤2×105
−231<=nums[i]<=231−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;
题目就变成了找到区间内递减区间的左端点,条件就是递减 ( a r r [ i ] > a r r [ i − 1 ] ) (arr[i] > arr[i - 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;
}
};
描述
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
数据范围: 对于 50%的数据, size≤104
对于100% 的数据, size≤105数组中所有数字的值满足 0≤val≤109
要求:空间复杂度 O(n),时间复杂度 O(nlogn)
输入描述:
题目保证输入的数组中没有的相同的数字
思路:
本题分类在二分查找/排序中,但实际上是一道归并的题目。我们面对这种逆序和题目,可以采取
暴力解法:两个for 循环就可以搞定。但是时间复杂度O(N2)
我们可以对暴力解法做优化:我们可以针对整个数组的左半区间找逆序对,再针对右半区间找逆序对,然后再在左区间中取一个数,右区间中取一个数(一左一右)找逆序对。关键点就是这个一左一右中取逆序对,如果我们实现左区间有序,右区间也有序,那么一左一右取逆序对的这个问题就可以大大简化:因为倘若左区间的一点下标 l e f t left left,右区间的一点下标 r i g h t right right,有 n u m s [ l e f t ] > n u m s [ r i g h t ] nums[left] > nums[right] nums[left]>nums[right],那么根据有序性,可以推出来 l e f t left left右边的所有左半区间的点都大于这个$ nums[right] ,也就是说,这个逆序和数可以直接加上这段长度而不用再一个一个遍历,直接让 ,也就是说,这个逆序和数可以直接加上这段长度而不用再一个一个遍历,直接让 ,也就是说,这个逆序和数可以直接加上这段长度而不用再一个一个遍历,直接让right++$,去判断 n u m s [ r i g h t ] nums[right] nums[right] 变大之后,左边还大不大于右边?如果大于,我们继续加上这段区间的长度,如果不大于,就是左边的值小了,让左边的点向右移动就可以了。
我们可以发现,这个思路实际上于归并排序的思路一样:取中间点,分别对左区间和右区间做递归调用(保证左右区间有序),双指针判断填入 t m p tmp 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; } };
描述
有一个长度为 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)
思路:
暴力解法,直接遍历数组就可以求最小值,时间复杂度 O ( N ) O(N) O(N)
优化:举个例子:[3, 4, 5, 1, 2] 可以看到数组是先递增 -> 最小值 ->递增
我们可以看出:旋转数组会有两段性:递增 -> 减 -> 递增,减的地方就是我们的最小值,而且根据原数组的递增性质,我们可以知道从减的地方开始(设为i),每个值都小于nums[0],因为 i 位置 一直到 n - 1 位置,都是增的 而且衔接到现在的 0 位置。所以我们就把问题变成了寻找区间左端点的二分查找问题。
但是本题目和leetcode 153 题不同的是,本题目是非减,而不是递增的数组,这就使得可以出现 [ 0 , 1 , 1 , 1 , 1 , 1 , 1 , 1 ] [0,1,1,1,1,1,1,1] [0,1,1,1,1,1,1,1]这样的数组。我们原来的思路就不成立了。
我们可以:分三个区间 [ l e f t , m i d ] [ m i d + 1 , r i g h t ] [left, mid][mid + 1, right] [left,mid][mid+1,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.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; } };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。