二分查找、排序（牛客）
题目来自牛客题目库 算法篇面试必刷TOP101。
BM17 二分查找-I(简单)
题目
请实现无重复数字的升序数组的二分查找
给定一个 元素升序的、无重复数字的整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标（下标从 0 开始），否则返回 -1
数据范围：0 ≤ len(nums) ≤ 2×10^5^ ， 数组中任意值满足∣val∣≤10^9^
进阶：时间复杂度 O(logn) ，空间复杂度O(1)
示例：
示例1：
输入：[-1,0,3,4,6,10,13,14],13
返回值：6
说明：13 出现在nums中并且下标为 6
示例2：
输入：[],3
返回值：-1
说明：nums为空，返回-1
示例3：
输入：[-1,0,3,4,6,10,13,14],2
返回值：-1
说明：2 不存在nums中因此返回 -1
备注：
数组元素长度在[0,10000]之间
数组每个元素都在 [-9999, 9999]之间。
解法 二分法
import java.util.*;
public class Solution {
public int search (int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right){
int mid = (left + right) / 2;
if(target < nums[mid]){
right = mid - 1;
}
else if(target > nums[mid]){
left = mid + 1;
}
else{
return mid;
}
}
return -1;
}
}
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^9^ 进阶：空间复杂度O(1) ，时间复杂度 O(n+m)
解法 二分查找(分治)
- step 1：首先获取矩阵的两个边长，判断特殊情况。
- step 2：首先以左下角为起点，若是它小于目标元素，则往右移动去找大的，若是他大于目标元素，则往上移动去找小的。
- step 3：若是移动到了矩阵边界也没找到，说明矩阵中不存在目标值。
图示：
public class Solution {
public boolean Find(int target, int [][] array) {
if(array.length == 0)
return false;
int m = array.length;
if(array[0].length == 0)
return false;
int n = array[0].length;
for(int i = m - 1, j = 0; i >= 0 && j <= n - 1; ){
if(array[i][j] == target){
return true;
}
else if(array[i][j] < target){
j++;
}
else if(array[i][j] > target){
i--;
}
}
return false;
}
}
BM19 寻找峰值(中等)
题目
给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。
1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于
2.假设 nums[-1] = nums[n] = −∞
3.对于所有有效的 i 都有 nums[i] != nums[i + 1]
4.你可以使用O(logN)的时间复杂度实现此问题吗？
数据范围：
1 ≤ nums.length ≤ 2×10^5^
−2^31^ ≤ nums[i] ≤ 2^31^−1
如输入[2,4,1,2,7,8,4]时，会形成两个山峰，一个是索引为1，峰值为4的山峰，另一个是索引为5，峰值为8的山峰，如下图所示：
解法1 遍历
从左到右遍历数组，时间复杂度O(n)
import java.util.*;
public class Solution {
public int findPeakElement (int[] nums) {
if(nums.length == 1)
return 0;
for(int i = 0; i < nums.length; i++){
if(i == 0){
if(nums[0] > nums[1]){
return 0;
}
}
else if(i == nums.length - 1){
if(nums[i] > nums[i - 1]){
return i;
}
}
else if(nums[i] > nums[i - 1] && nums[i] > nums[i + 1]){
return i;
}
}
return 0;
}
}
解法2 二分
因为题目将数组边界看成最小值，而我们只需要找到其中一个波峰，因此只要不断地往高处走，一定会有波峰。
- step 1：二分查找首先从数组首尾开始，每次取中间值，直到首尾相遇。
- step 2：如果中间值的元素大于它右边的元素，说明往右是向下，我们不一定会遇到波峰，但是那就往左收缩区间。
- step 3：如果中间值大于右边的元素，说明此时往右是向上，向上一定能有波峰，那我们往右收缩区间。
- step 4：最后区间收尾相遇的点一定就是波峰。
图示：
时间复杂度O(logn)
import java.util.*;
public class Solution {
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;
}
}
这个解法的划分区间一定是right = mid; left = mid + 1。
BM20 数组中的逆序对(中等)？
题目
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
数据范围： 对于 50% 的数据, size≤10^4^ 对于 100% 的数据, size≤10^5^
数组中所有数字的值满足 0≤val≤10^9^
要求：空间复杂度O(n)，时间复杂度O(logn)
输入描述：
题目保证输入的数组中没有的相同的数字
示例：
示例1：
输入：[1,2,3,4,5,6,7,0]
返回值：7
示例2：
输入：[1,2,3]
返回值：0
解法 归并
具体做法：
- step 1： 划分阶段：将待划分区间从中点划分成两部分，两部分进入递归继续划分，直到子数组长度为1.
- step 2： 排序阶段：使用归并排序递归地处理子序列，同时统计逆序对，因为在归并排序中，我们会依次比较相邻两组子数组各个元素的大小，并累计遇到的逆序情况。而对排好序的两组，右边大于左边时，它大于了左边的所有子序列，基于这个性质我们可以不用每次加1来统计，减少运算次数。
- step 3： 合并阶段：将排好序的子序列合并，同时累加逆序对。
图示：
public class Solution {
public int mod = 1000000007;
public int mergeSort(int left, int right, int [] data, int [] temp){
//停止划分
if(left >= right)
return 0;
//取中间
int mid = (left + right) / 2;
//左右划分合并
int res = mergeSort(left, mid, data, temp) + mergeSort(mid + 1, right, data, temp);
//防止溢出
res %= mod;
int i = left, j = mid + 1;
for(int k = left; k <= right; k++)
temp[k] = data[k];
for(int k = left; k <= right; k++){
if(i == mid + 1)
data[k] = temp[j++];
else if(j == right + 1 || temp[i] <= temp[j])
data[k] = temp[i++];
//左边比右边大，答案增加
else{
data[k] = temp[j++];
// 统计逆序对
res += mid - i + 1;
}
}
return res % mod;
}
public int InversePairs(int [] array) {
int n = array.length;
int[] res = new int[n];
return mergeSort(0, n - 1, array, res);
}
}
很难，没看懂。
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：
输入：[3,4,5,1,2]
返回值：1
示例2：
输入：[3,100,200,3]
返回值：3
解法 二分法
算法流程：
- 初始化： 声明 left, right 双指针分别指向 array 数组左右两端
- 循环二分： 设 mid = (left + right) / 2 为每次二分的中点（ “/” 代表向下取整除法，因此恒有 left ≤ mid）
- 当 array[mid] > array[right] 时： mid 一定在 左排序数组 中，即旋转点 x 一定在 [mid + 1, right] 闭区间内，因此执行 left = mid + 1
- 当 array[mid] < array[right] 时： mid 一定在 右排序数组 中，即旋转点 x 一定在[left, mid]闭区间内，因此执行 right = mid
- 当 array[mid] = array[right] 时： 无法判断旋转点 x 在 [left, mid] 还是 [mid + 1, right] 区间中。解决方案： 执行 right = right - 1 缩小判断范围
- 返回值： 当 left = right 时跳出二分循环，并返回 旋转点的值 array[left] 即可。
图解：
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
int left = 0;
int right = array.length - 1;
while (left <= right) {
int mid = (left + right) / 2;
if (array[mid] > array[right]) {
left = mid + 1;
}
else if(array[mid] < array[right]){
right = mid;
}
else{
right--;
}
}
return array[left];
}
}
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)
解法 双指针
比较的时候，数字前导零不便于我们比较，因为我们不知道后面会出现多少前导零，因此应该将点之间的部分转化为数字再比较才方便。
import java.util.*;
public class Solution {
public int compare (String version1, String version2) {
// 字符串的length()需要加括号，数组的length不需要加括号
int n1 = version1.length();
int n2 = version2.length();
int i = 0, j = 0;
// 其中一个字符串结束
while(i < n1 || j < n2){
long num1 = 0;
// Java中的字符串可以用charAt()方法访问字符
while(i < n1 && version1.charAt(i) != '.'){
// 将'.'前的部分转化为十进制数
num1 = num1 * 10 + (version1.charAt(i) - '0');
i++;
}
// 跳过'.'
i++;
long num2 = 0;
while(j < n2 && version2.charAt(j) != '.'){
num2 = num2 * 10 + (version2.charAt(j) - '0');
j++;
}
j++;
if(num1 > num2)
return 1;
if(num1 < num2)
return -1;
}
return 0;
}
}