二分查找算法题
1.二分查找搜索算法(注意怎么和面试官描述你的思路)
- 最普通的二分查找(注意这里left<=right)
int left = 0;
int right = nums.length-1;
while(left<=right){
int mid = (left+right)/2;
if(nums[mid]>target){
right--;
}else if(nums[mid]<target){
left++;
}else{
return mid;
}
}
- 寻找峰值（其实这里只需要根据题目要求，如果我想要的是满足条件的最后一个数，就是right = mid-1，如果是第一个数就是left= mid+1），注意如果是right = mid-1的话，mid = left+(right-left+1)/2;+1别忘了
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-left+1)/2;
if(nums[mid]>nums[mid-1]){
left = mid;
}else{
right = mid -1;
}
}
return left;
}
}
3.1旋转数组的最小值(顺序)--就是上课的套路
public int findMin(int[] nums) {
public int findMin(int[] nums) {
int left = 0;
int key = nums[0];
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < key) {
right = mid;
} else {
left = mid + 1;
}
}
if (nums[left] >= key)
return key;
return nums[left];
}
}
3.2旋转数组的最小值(非降序)也就是存在不增不减和升序的情况(背就行)
public int minNumberInRotateArray (int[] nums) {
if(nums.length==0){
return 0;
}
int left = 0,right = nums.length-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 = mid;
}else{
right--;
}
}
return nums[left];
}
4.比较版本号
public int compare (String version1, String version2) {
int n = version1.length();
int m = version2.length();
char[]s1 = version1.toCharArray();
char[]s2 = version2.toCharArray();
int i =0 , j =0 ;
while(i<n&&j<m){
int res1 = 0;
int res2 = 0;
while(i<n&&s1[i]!='.'){
res1= res1*10 + (s1[i]-'0');
i++;
}
while(j<m&&s2[j]!='.'){
res2= res2*10 + (s2[j]-'0');
j++;
}
if(res1>res2)
return 1;
else if(res1<res2)
return -1;
i++;
j++;
}
while(i<m){
int res11 = 0;
while(i<m&&s1[i]!='.'){
res11 = res11*10+(s1[i]-'0');
i++;
}
if(res11>0)
return 1;
i++;
}
while(j<n){
int res22 = 0;
while(j<n&&s2[j]!='.'){
res22 = res22*10+(s2[j]-'0');
j++;
}
if(res22>0)
return -1;
j++;
}
return 0;
}
- 逆序对
import java.util.*;
public class Solution {
public int InversePairs (int[] nums) {
return (int)mergeSort(nums,0,nums.length-1);
}
public long mergeSort(int[]nums,int left, int right){
if(left>=right){
return 0;
}
int mid = left+(right-left)/2;
long ret = 0;
ret+= mergeSort(nums,left,mid);
ret+= mergeSort(nums,mid+1,right);
int cur1 = left;
int cur2 = mid+1;
while(cur1<=mid){
while(cur2<=right&&nums[cur2]>=nums[cur1]){
cur2++;
}
if(cur2>right)
break;
ret+= right-cur2+1;
cur1++;
}
cur1 = left;
cur2 = mid+1;
int[] tmp= new int[nums.length];
int i = 0;
while(cur1<=mid&&cur2<=right){
if(nums[cur1]<nums[cur2]){
tmp[i++] = nums[cur2++];
}else{
tmp[i++] = nums[cur1++];
}
}
while(cur1<=mid){
tmp[i++] = nums[cur1++];
}
while(cur2<=right){
tmp[i++] = nums[cur2++];
}
for(int j = left;j<=right;j++){
nums[j] = tmp[j-left];
}
return ret%1000000007;
}
}