测试开发备战秋招面试6-牛客刷题二分查找/排序篇

努力了那么多年,回头一望,几乎全是漫长的挫折和煎熬。对于大多数人的一生来说,顺风顺水只是偶尔,挫折、不堪、焦虑和迷茫才是主旋律。我们登上并非我们所选择的舞台,演出并非我们所选择的剧本。继续加油吧！

1、二分查找-I

2、二维数组的查找

3、寻找峰值

4、数组中的逆序对

5、旋转数组的最小数字

6、比较版本号

1、二分查找-I

题目链接：二分查找-I_牛客题霸_牛客网
思路：双指针实现即可。

Java版：

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param nums int整型一维数组 * @param target int整型 * @return int整型*/public int search (int[] nums, int target) {// write code hereint low = 0, high = nums.length ;if(nums.length == 0){return -1 ;}while(low<=high){int mid = (low+high) >> 1 ;if(nums[mid] > target){high = mid - 1;}else if(nums[mid] < target){low = mid + 1 ;}else{return mid ;}}return -1 ;}
}

Python：

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @param target int整型 
# @return int整型
#
class Solution:def search(self , nums: List[int], target: int) -> int:# write code herelow = 0high = len(nums)if low == high:return -1 while low <= high:mid = (low + high) >> 1if nums[mid] > target:high = mid - 1elif nums[mid] < target:low = mid + 1else:return mid return -1

2、二维数组的查找

题目链接：二维数组中的查找_牛客题霸_牛客网

思路：从右上角开始搜索，不断的往左或者往下走即可，时复：O(M+N),空复：O(1)

Java版：

public class Solution {public boolean Find(int target, int [][] array) {/** for(int i=0; i<array.length; i++){for(int j=0; j<array[0].length; j++){if(array[i][j] == target){return true ;}}}return false ;*///从右上角开始线性搜索int left = 0, right = array[0].length-1 ;while(left < array.length && right >=0){if(array[left][right] == target){return true ;}else if(array[left][right] > target){right -- ;}else{left ++ ;}}return false ;}
}

Python版：

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param target int整型 
# @param array int整型二维数组 
# @return bool布尔型
#
class Solution:def Find(self , target: int, array: List[List[int]]) -> bool:# write code herei = 0j = len(array[0]) - 1 while i < len(array) and j >= 0:if array[i][j] == target:return Trueelif array[i][j] > target:j = j - 1else:i = i + 1 return False

3、寻找峰值

题目链接：寻找峰值_牛客题霸_牛客网

思路：有点二分的意思，就是从中间往两边跑，左边大往左边跑，右边大往右边跑。
Java版：

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param nums int整型一维数组 * @return int整型*/public int findPeakElement (int[] nums) {// write code here//这个找波峰有个寻找逻辑，从中间开始找，右边大于左边，往右招，反之，往左找到int left = 0, right = nums.length-1 ;while(left < right){int mid = (left + right) >> 1 ;if(nums[mid] > nums[mid+1]){right = mid ;}else{left = mid + 1;}}return right ;}
}

4、数组中的逆序对

题目链接：数组中的逆序对_牛客题霸_牛客网

思路：先划分，后合并，合并后并排序，同时计算逆序对。分而治之的思想。

Java版：

public class Solution {int cnt = 0 ;public int InversePairs(int [] array) {//先分后治，先划分为每个分组只有一个元素，然后合并统计逆序并排序mergeSort(array, 0, array.length-1) ;return cnt ;}public void mergeSort(int [] array, int left, int right){int mid = (left + right) >> 1 ;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 [] tmp = new int [right - left + 1] ;int l = left, r = mid + 1;int c = 0 ;while(l<=mid && r<=right){if(array[l] <= array[r]){tmp[c++] = array[l++];}else{tmp[c++] = array[r++] ;cnt += mid - l + 1 ;cnt %= 1000000007 ;}}while(l<=mid){tmp[c++] = array[l++] ;}while(r<=right){tmp[c++] = array[r++] ;}int s = left ;for(int num:tmp){ //每次排序后需要回传到原来的数组中array[s++] = num;}}
}

Python版：

class Solution:def InversePairs(self , data: List[int]) -> int:# write codeglobal  cc = 0self.mergeSort( data,   0, len(data) - 1)return cdef mergeSort(self, data : List[int],   left:int, right:int) :mid = (left + right) >> 1if(left < right):self.mergeSort( data,  left, mid)self.mergeSort(data,  mid+1, right)self.merge(data,  left, mid, right)def merge(self, data : List[int],  left:int, mid:int, right:int):global cr = mid + 1l = lefti = 0lst = [0 for x in range(right-left+1)]while l<=mid and r<=right:if data[l] <= data[r]:lst[i] = data[l]l = l + 1else:lst[i] = data[r]c = c + mid - l + 1c = c % 1000000007r = r + 1i = i + 1while l<=mid:lst[i] = data[l]i = i + 1l = l + 1while r<=right:lst[i] = data[r]i = i + 1r = r + 1j = leftfor v in lst:data[j] = vj = j + 1

5、旋转数组的最小数字

题目链接：旋转数组的最小数字_牛客题霸_牛客网

思路：二分思想，将中间的和最右边的比较，然后缩小搜索区间即可。

Java版：

import java.util.ArrayList;
public class Solution {public int minNumberInRotateArray(int [] array) {//二分思想int left = 0, right = array.length - 1 ;while(left < right){int mid = (left + right) >> 1 ;if(array[mid] > array[right]){left = mid + 1;}else if(array[mid] < array[right]){right = mid;}else{right -- ;}}return array[left] ;}
}

6、比较版本号

题目链接：比较版本号_牛客题霸_牛客网
思路：以.号为截取点，每次截取转成整数，然后对比即可。

Java版：

import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** 比较版本号* @param version1 string字符串 * @param version2 string字符串 * @return int整型*/public int compare (String version1, String version2) {// write code hereint len1 = version1.length(), len2 = version2.length() ;int i=0, j=0 ;while(i<len1 || j<len2){int num1 = 0 ;while(i<len1 && version1.charAt(i) != '.'){num1 = num1 * 10 + (version1.charAt(i++) - '0') ; }i ++ ;int num2 = 0 ;while(j<len2 && version2.charAt(j) != '.'){num2 = num2 * 10 + (version2.charAt(j++) - '0') ;}j ++ ;if(num1 > num2){return 1 ;}if(num1 < num2){return -1 ;}}return 0 ;}
}