剑指Offer第四天

题1:数组中重复数字
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

class Solution {
public int findRepeatNumber(int[] nums) {
Set<Integer> set = new HashSet<>();
for(int num: nums){
if(set.contains(num)){
return num;
}
set.add(num);
}
return 0;
}
}
题2:在排序数组中查找数字
统计一个数字在排序数组中出现的次数。

class Solution {
public int search(int[] nums, int target) {
int head = 0;
int length = nums.length;
int last = length-1;
while(head < last){
int mid = (head + last + 1)/2;
if(nums[mid] <= target){
head = mid;
}
if(nums[mid] > target){
last = mid-1;
}
}
int sum = 0;
while(last >= 0 && nums[last] == target && last-->=0){
sum++;
}
return sum;
}
}

题3:0~n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。 
有一说一,这道题测试用例有个[0]是真的搞。。
class Solution {
public int missingNumber(int[] nums) {
int length = nums.length;
int head = 0;
int last = length-1;
while(head <= last){
int mid = (head + last) >> 1;
if(nums[mid] == mid){
head = mid + 1;
}else{
last = mid - 1;
}
}
return head;
}
}
![[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-t5P5gFvy-1631028626388)(剑指Offer4/image-20210907231040206.png)]](https://img-blog.csdnimg.cn/ad0f2ca3d6314836a501bc610ff35761.png?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBAbm9uYmlvY2xvY2s=,size_19,color_FFFFFF,t_70,g_se,x_16)
总结:见到有序,就用二分
int left = 0;
int length = nums.length;
int right = length - 1;
while(left <= right){
int mid = right - (right-left)/2;
if(nums[mid] <= xx){
left = mid;
}else{
right = mid-1;
}
}
Q:如何很快的区分是while(left<right)还是whlile(left<=right)?
|