- 17 二分查找-I
- 18 二维数组中的查找
- 19 寻找峰值
- 20 数组中的逆序对
- 21 旋转数组的最小数字
- 22 比较版本号
17 二分查找-I这是牛客必刷题第二个知识点(二分查找)，大家一起共勉！
题目描述：请实现无重复数字的升序数组的二分查找
要求：给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标（下标从 0 开始），否则返回 -1
输入：[-1,0,3,4,6,10,13,14],13
返回值：6
说明：13 出现在nums中并且下标为 6输入：[],3
返回值：-1
说明：nums为空，返回-1
题目解法：常规的二分查找方法
public int search (int[] nums, int target) {
// 直接二分查找
int left = 0;
int right = nums.length-1;
while(left <=right){
int mid = (right + left)/2;
//int mid = left + (right - left)/2;
if(nums[mid] == target)
return mid;
else if(nums[mid]>target)
right = mid-1;
else if(nums[mid]<target)
left = mid+1;
}
return -1;
}
题目描述
在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
给定 target = 7，返回 true。
给定 target = 3，返回 false。
方法一：暴力解法
思路分析：直接遍历一遍数组，即可判断目标target是否存在。
复杂度分析
时间复杂度：O(n^2)，因为最坏情况下，数组中的元素都需要遍历一次。
空间复杂度：O(1)
// 这种方法不推荐使用，时间复杂度较高
public bool Find(int target, vector<vector<int> > array) {
// 判断数组是否为空
if (array.size() ==0 || array[0].size() ==0) return false;
for (const auto& vec : array) {
for (const int val : vec) {
if (val == target)
return true;
}
}
return false;
}
方法二：二分查找
假设arr数组，val，tar如下图所示：
如果我们把二分值定在右上角或者左下角，就可以进行二分。这里以右上角为例，左下角可自行分析：
具体步骤：
1）我么设初始值为右上角元素，arr[0][5] = val，目标tar = arr[3][1]
2）接下来进行二分 *** 作：
3）如果val == target,直接返回
4）如果 tar > val, 说明target在更大的位置，val左边的元素显然都是 < val，间接 < tar，说明第 0 行都是无效的，所以val下移到arr[1][5]
5）如果 tar < val, 说明target在更小的位置，val下边的元素显然都是 > val，间接 > tar，说明第 5 列都是无效的，所以val左移到arr[0][4]
6）继续步骤2）
public boolean Find(int target, int [][] array) {
//判断数组是否为空
int m = array.length;
if(m==0) return false;
int n = array[0].length;
if(n==0) return false;
//设置右上角元素
int r = 0, c = n-1;
while(r < m && c >= 0){
if(target == array[r][c]) return true;
else if(target > array[r][c]) ++r;
else --c;
}
return false;
}
复杂度分析
时间复杂度：O(m+n) ，其中m为行数，n为列数，最坏情况下，需要遍历m+n次。
空间复杂度：O(1)
同理：也可以设置左下角val，然后target值大于val，那么直接列增加【c++】，如果小于val值，那么直接行减小【r–】
19 寻找峰值题目描述：
给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。
1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
2.假设 nums[-1] = nums[n] = −∞
3.对于所有有效的 i 都有 nums[i] != nums[i + 1]
如输入[2,4,1,2,7,8,4]时，会形成两个山峰，一个是索引为1，峰值为4的山峰，另一个是索引为5，峰值为8的山峰，如下图所示：
输入：[2,4,1,2,7,8,4]
返回值：1
说明：4和8都是峰值元素，返回4的索引1或者8的索引5都可以
分析：
nums[mid] < nums[mid + 1]说明在“上坡”，则可以使left = mid +1（因为mid肯定不是峰值），向“峰”处压缩
nums[mid] > nums[mid + 1]说明在“下坡”，则应该使right =mid（mid可能是峰值），往“峰”处压缩
step 1：二分查找首先从数组首尾开始，每次取中间值，直到首尾相遇。
step 2：如果中间值的元素大于它右边的元素，说明往右是向下，我们不一定会遇到波峰，但是那就往左收缩区间。
step 3：如果中间值大于右边的元素，说明此时往右是向上，向上一定能有波峰，那我们往右收缩区间。
step 4：最后区间收尾相遇的点一定就是波峰。
public int findPeakElement (int[] nums) {
int left = 0;
int right = nums.length - 1;
//二分法
while(left < right){
int mid = (left + right) / 2;
//右边是往下，不一定有坡峰
if(nums[mid] > nums[mid + 1])
right = mid;
//右边是往上，一定能找到波峰
else
left = mid + 1;
}
//其中一个波峰
return right;}
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
示例1
输入：[1,2,3,4,5,6,7,0]
返回值：7
示例2
输入：[1,2,3]
返回值：0
方法一：暴力解法
public int InversePairs(int [] array) {
int res = 0;
int len = array.length;
for(int i = 0;i < len-1;i++){
for(int j=i;j
if(array[i]>array[j]){
res +=1;
res =res % 1000000007;
}
}
}
return res;
}
但是如果数据量级比较大，就会超时。
方法二：归并方法
先分：分呢，就是将数组分为两个子数组，两个子数组分为四个子数组，依次向下分，直到数组不能再分为止！
后并：并呢，就是从最小的数组按照顺序合并，从小到大或从大到小，依次向上合并，最后得到合并完的顺序数组！
介绍完归并排序，我们来说说归并统计法，我们要在哪个步骤去进行统计呢？
归并统计法，关键点在于合并环节，在合并数组的时候，当发现右边的小于左边的时候，此时可以直接求出当前产生的逆序对的个数。
public class Solution {
int count = 0;
public int InversePairs(int [] array) {
// 长度小于2则无逆序对
if(array.length < 2)
return 0;
// 进入归并
mergeSort(array,0,array.length-1);
return count;
}
public void mergeSort(int[] array,int left,int right){
// 找分割点
int mid = left+(right-left)/2;
if(left < right){
// 左子数组
mergeSort(array,left,mid);
// 右子数组
mergeSort(array,mid+1,right);
// 并
merge(array,left,mid,right);
}
}
public void merge(int[] array,int left,int mid,int right){
// 创建临时数组，长度为此时两个子数组加起来的长度
int[] arr = new int[right-left+1];
// 临时数组的下标起点
int c = 0;
// 保存在原数组的起点下标值
int s = left;
// 左子数组的起始指针
int l = left;
// 右子数组的起始指针
int r = mid+1;
while(l <= mid && r <= right ){
// 当左子数组的当前元素小的时候，跳过，无逆序对
if(array[l] <= array[r]){
// 放入临时数组
arr[c++] = array[l++];
}else{ // 否则，此时存在逆序对
// 放入临时数组
arr[c++] = array[r++];
// 逆序对的个数为 左子数组的终点- 当前左子数组的当前指针
count += mid+1-l;
count %= 1000000007;
}
// 左子数组还有元素时，全部放入临时数组
while(l <= mid)
arr[c++] = array[l++];
// 右子数组还有元素时，全部放入临时数组
while(r <= right)
arr[c++] = array[r++];
// 将临时数组中的元素放入到原数组的指定位置
for(int num:arr){
array[s++] = num;
}
}
}
题目描述：
有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。
输入：[3,4,5,1,2]
返回值：1
输入：[3,100,200,3]
返回值：3
方法一：暴力解法：直接遍历一遍数组，即可找到最小值。但是本题的附加条件就没有用上。肯定不是面试官所期望的答案
方法二：二分查找
优点：可将遍历法的线性级别 时间复杂度降低至 对数级别
分析：找最小值，array[m] > array[j] 那么范围就是【m+1，j】；array[m] < array[j]，那么其中包含m的值，所以范围【i,m】
具体步骤：
1、初始化： 声明 i, j 双指针分别指向 array 数组左右两端
2、循环二分： 设 m = (i + j) / 2 为每次二分的中点（ “/” 代表向下取整除法，因此恒有 i≤m+1、当 array[m] > array[j] 时： m 一定在左排序数组中，即旋转点 x 一定在 [m + 1, j] 闭区间内，因此执行 i = m + 1
2、当 array[m] < array[j] 时：m 一定在右排序数组中，即旋转点 x 一定在[i, m]闭区间内，因此执行 j = m
3、当 array[m] = array[j] 时： 无法判断 m 在哪个排序数组中，即无法判断旋转点 x 在 [i, m] 还是 [m + 1, j] 区间中。解决方案： 执行 j = j - 1 缩小判断范围
3、返回值： 当 i = j 时跳出二分循环，并返回旋转点的值 array[i] 即可。
public int minNumberInRotateArray(int [] array) {
// 特殊情况判断
if (array.length== 0) {
return 0;
}
// 左右指针i j
int i = 0, j = array.length - 1;
// 循环
while (i < j) {
// 找到数组的中点 m
int m = (i + j) / 2;
// m在左排序数组中，旋转点在 [m+1, j] 中
if (array[m] > array[j]) i = m + 1;
// m 在右排序数组中，旋转点在 [i, m]中
else if (array[m] < array[j]) j = m;
// 缩小范围继续判断
else j--;
}
// 返回旋转点
return array[i];
}
题目描述：牛客项目发布项目版本时会有版本号，比如1.02.11，2.14.4等等
现在给你2个版本号version1和version2，请你比较他们的大小。
比较规则：
一. 比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较忽略任何前导零后的整数值。比如"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
输入：“1.1”,“2.1”
返回值：-1
说明：version1 中下标为 0 的修订号是 “1”，version2 中下标为 0 的修订号是 “2” 。1 < 2，所以 version1 < version2，返回-1示例2
输入：“1.1”,“1.01”
返回值：0
说明：version2忽略前导0，为"1.1"，和version相同，返回0
示例3
输入：“1.1”,“1.1.1”
返回值：-1
说明：“1.1"的版本号小于"1.1.1”。因为"1.1"的版本号相当于"1.1.0"，第3位修订号的下标为0，小于1，所以version1 < version2，返回-1
示例4
输入：“2.0.1”,“2”
返回值：1
说明：version1的下标2>version2的下标2，返回1
示例5
输入：“0.226”,“0.36”
返回值：1
说明：226>36，version1的下标2>version2的下标2，返回1
解题分析：双指针，使用v1和v2这两个值来分别计算版本号每个被’.'分割的块的版本号的大小，如果不相等，则进行比较
具体步骤：
1、初始化双指针v1,v2分别为0
2、分别对两个版本字符串进行遍历
1、遍历第一个版本字符串(索引 i)，以 ‘.’ 为分割点（循环结束条件），计算每一块的版本号大小，记为 V1；
2、遍历第二个版本字符串(索引 j)，以 ‘.’ 为分割点（循环结束条件），计算每一块的版本号大小，记为 V2；
3、对比V1, V2
1、：继续遍历两个版本字符串 ,
2、：直接返回 1
3、：直接返回 -1
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 比较版本号
* @param version1 string字符串
* @param version2 string字符串
* @return int整型
*/
public int sgn(int a ,int b){
if(a>b) return 1;
else if(a<b) return -1;
else return 0;
}
public int compare (String version1, String version2) {
// 双指针，设置指针,从开头处开始
int i=0, j=0;
int l1 = version1.length(),l2 = version2.length();
// 设置默认块
int v1 = 0,v2 = 0;
// 两个字符串均未跑完
while (i < l1 || j < l2) {
// 计算串1的当前块，如果字符串已经遍历完则什么也不做，用默认值0代替块中数据
// 遇到点就跳出循环
while (i < l1 && version1.charAt(i) != '.')
v1 = v1*10 + (version1.charAt(i++) - '0');
// 串2同理
while (j < l2 && version2.charAt(j) != '.')
v2 = v2*10 + (version2.charAt(j++)- '0');
// 如果两个块中的数不一样，直接返回
if (v1 != v2) return sgn(v1, v2);
v1 = v2 = 0; // 恢复默认值
i++;
j++; // 此时i和j要么出去了，要么遇到了点，跳过，出去了也无所谓
}
return 0;
}
}
时间复杂度。其中 和 指的是输入字符串的长度。遍历版本字符串时间
空间复杂度：使用双指针及其他常数级空间变量
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）