在一个长度为 n 的数组nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
题解：遍历数组，将数据存储在map中，每次循环均判断map中是否存在：
-若存在，则直接break，返回结果；
-若不存在，则将数据存储在map集合中继续遍历。
public int findRepeatNumber(int[] nums) {
Map map = new HashMap();
int i=0;
for (i=0;i
剑指 Offer 53 - I. 在排序数组中查找数字 I
题目：
统计一个数字在排序数组中出现的次数。
题解1：
- 定义helper1函数，返回target值最后一次出现的下标；
- 判断条件为nums[mid]<=tar，即不断的将low值右移，返回low值。
public int search(int[] nums, int target) {
return helper1(nums, target) - helper1(nums, target - 1);
}
int helper1(int[] nums, int tar) {
int low = 0, high = nums.length - 1;
while(low <= high) {
int mid = (low + high) / 2;
if(nums[mid] <= tar) low = mid + 1;
else high = mid - 1;
}
return low;
}
题解2：
- 定义helper2函数，返回target值第一次出现的下标；
- 判断条件为nums[mid]>=tar，即不断的讲high值左移，返回high值。
public int search(int[] nums, int target) {
return helper1(nums, target+1) - helper1(nums, target);
}
int helper2(int[] nums, int tar) {
int low = 0, high = nums.length - 1;
while(low <= high) {
int mid = (low + high) / 2;
if(nums[mid] >= tar) high = mid - 1;
else low = mid + 1;
}
return high;
}
剑指 Offer 53 - II. 0～n-1中缺失的数字
题目：
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
题解1：
等差数列求和sum1减去数组之和sum2
public int missingNumber(int[] nums) {
int sum1 = (nums.length)*(nums.length+1)/2;
int sum2=0;
for (int i = 0;i
题解2：
返回数组元素nums[i]和i不相等的下标i
public int missingNumber(int[] nums) {
int len = nums.length;
for (int i = 0; i < len; i++) {
if (i != nums[i]) return i;
}
return len;
}
34. 在排序数组中查找元素的第一个和最后一个位置
题目：
给定一个按照升序排列的整数数组nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。如果数组中不存在目标值 target，返回 [-1, -1]
题解：
- 利用剑指 Offer 53 - I. 在排序数组中查找数字 I 中helper1和helper2函数分别得到结束位置和开始位置;
- 特殊处理一下数组中不存在目标值 target的情况：利用内置二分查找函数Arrays.binarySearch(nums,target)，若小于0则代表有序数组中不存在该值，返回[-1,-1]。
public int[] searchRange(int[] nums, int target) {
int[] res = new int[2];
if (Arrays.binarySearch(nums,target)>=0){
res[1] = helper1(nums, target)-1;
res[0] = helper2(nums, target)+1;
} else {
res[0] = -1;
res[1] = -1;
}
return res;
}
int helper1(int[] nums, int tar) {
int low = 0, high = nums.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (nums[mid] <= tar) low = mid + 1;
else high = mid - 1;
}
return low;
}
int helper2(int[] nums, int tar) {
int low = 0, high = nums.length - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (nums[mid] >= tar) high = mid - 1;
else low = mid + 1;
}
return high;
}
暴风雨结束后，你不会记得自己是怎样活下来的，你甚至不确定暴风雨是否真的结束了。但有一件事是确定的:当你穿过了暴风雨，你早已不再是原来那个人。
