leetcode剑指Offer第四天
从数组中重复的数字
Easy 原题连接：数组中重复的数字
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
提示：
2 <= n <= 100000
解题思路
方法一：已知总数组长度和数范围，直接创建对应大小的空数组，遍历总数组，增加空数组中对应位值，判断值是否到2，到2返回（简单，空数组浪费空间）
方法二：遍历总数组，利用HashSet存储以及查看过的数据，在每次遍历时查看HashSet是否已经存储，已存储就返回
方法三：遍历数组，将nums[n] 的位置放入 n 值，如果已经放过了却还需要放（重复）就返回该值。（时间复杂：O( N ), 空间复杂：O( 1 ) ）
方法三思路：数组长度为n，数字范围为1-n，因为存在重复项，所以数组与数字是存在一对多的关系。对于一个nums[ i ]，只有两种可能：nums[ i ] = i ，即他的值就是当前位置的数组偏移量（数组下标），又或者不是；前者我们不做改动，后者我们交换它与 nums[ nums[ i ] ] 位置的值，使得 nums[ nums[ i ] ]成为前者，再判断当前位置，直到成为前者，继续遍历或者发现同一个位置又两个 i ，返回 i ，比如：在数组中有两个3时，nums[ 3 ]的位置会需要填入两个3，我们在第一次发现3的时候会将其填入，再次发现3的时候，对比已经知道了nums[ 3 ] = 3，所以3重复，返回3
Java代码
class Solution {
public int findRepeatNumber(int[] nums) {
int i=0;
while(i < nums.length) {
// 位置值本就正确
if(nums[i] == i) {
i++;
continue;
}else {
// 要交换的位置已经是正确的了，发现重复
if(nums[i] == nums[nums[i]]) {
return nums[i];
}
// 将nums[ nums[i] ]转为正确对应，i没有++，继续判断该位置
swap(nums, i, nums[i]);
}
}
return -1;
}
// 注：这个是交换方法，用于交换nums中a,b位置的值，因为是引用传递所以不用返回
// 更加注意：这个方法只能用于你确定nums中你要交换的部分一定不存在相同的值，毕竟a^a=0,a^0=a
public void swap(int[] nums, int a, int b){
nums[a] = nums[a]^nums[b];
nums[b] = nums[a]^nums[b];
nums[a] = nums[a]^nums[b];
}
}
/**
O(n) O(n)
方法一：数组存储存储
int[] fin = new int[nums.length];
for(int i =0; i< nums.length; i++) {
fin[nums[i]]++;
if(fin[nums[i]]>1) return nums[i];
}
return -1;
O(n) O(n)
方法二：HashSet存储
HashSet<Integer> sets = new HashSet<>();
for(int i =0; i< nums.length; i++) {
if(sets.contains(nums[i])) return nums[i];
sets.put(nums[i]);
}
return -1;
*/
查找：二分查找
在分析下面两题前，先复习一下 二分查找 以及其边界问题吧
首先，什么时候能用上二分：数组满足某种要求，你能确定存在一条线将数组划分为两个部分，一个满足要求，一个不满足
最常见的就是在排序数组中找到某个边界
// 在nums中找到target的位置
public static int bs(int[] nums , int target) {
int l = 0, r = nums.length-1;
while(l<=r) {
// 取中间值
int mid = l+(r-l)>>1;
// 中间值大，取左边
if(nums[mid] > target) {
r = mid - 1;
// 中间值小，取右边
}else if(nums[mid] < target) {
l = mid + 1;
// 正好，取了
}else {
return mid;
}
}
// 没有对应target的值
return -1;
}
这个二分有什么问题？target的值需要唯一，试想一个[ 1,2,3,3,3,4,5 ]，我们希望找出大于等于3的位置，就不能如上述来写二分
如上面的小例子，当我们需要了解对某个范围的第一个/最后一个的位置问题，首先要明白二分中左右边界，即 l 和 r 的作用。
对于一段符合要求的数组，现在可以被两条线分为三个部分：【小于target的部分 1 | 2 等于target的部分 3 | 4 大于target的部分】
你可能注意到我标上的四个数字了，其中，1和3代表的就是最后一个的位置问题（1 最后一个小于target的数，3 最后一个小于等于target的数），2和4代表的是第一个位置问题（2 第一个大于等于target的数， 4 第一个大于target的数）
第一个大于/大于等于target的值的位置问题
// 在nums中找到第一个大于target的位置
public static int bs(int[] nums , int target) {
int l = 0, r = nums.length-1;
while(l<=r) {
int mid = l+(r-l)>>1;
// 注意，此处的 = 判断，加上了=就是将target当作右边界，也就是在上述的1 2中做判断
if(nums[mid] >= target) {
r = mid - 1;
}else {
l = mid + 1;
}
}
// 试想一下 l 的变化，每次都取mid中间值+1的位置，mid作为中间值，mid+1自然是第一个大于mid的位置
return l;
}
最后一个小于/小于等于target的值的位置问题
// 在nums中找到第一个小于等于target的位置
public static int bs(int[] nums , int target) {
int l = 0, r = nums.length-1;
while(l<=r) {
int mid = l+(r-l)>>1;
// 注意，对比上面的代码，这里没加= ，就是将target当作左边界，也就是在上述的3 4中做判断
if(nums[mid] > target) {
r = mid - 1;
}else {
l = mid + 1;
}
}
// 试想一下 r 的变化，每次都取mid中间值-1的位置，mid作为中间值，mid-1自然是最后一个小于mid的位置
return r;
}
当然，上述证明还是口述化了一点，不过大家可以实际结合题目试试
综上，简单来说，l 用于判断 第一个 符合条件的位置，r 用于判断 最后一个 符合条件的位置，判断中的 = 判断target作为左边界还是右边界（前提是target存在）
在排序数组中查找数字
Easy 原题连接：在排序数组中查找数字 I
统计一个数字在排序数组中出现的次数。
示例：
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109
解题思路
找到最后一个小于等于target的值，找到第一个大于target的值，两者取差-1
Java代码
class Solution {
public int search(int[] nums, int target) {
// 非递减数组，找到最后一个小于等于target的值，找到第一个大于target的值，差值-1即可
// 二分查找
int i, j;
for(i=0,j=nums.length-1; i<=j; ) {
int mid = i+(j-i)>>1;
if(nums[mid] > target) {
j = mid-1;
}else {
i = mid+1;
}
}
int lastSmo = i;
for(i=0,j=nums.length-1; i<=j; ) {
int mid = i+(j-i)>>1;
System.out.println(mid);
if(nums[mid] >= target) {
j = mid-1;
}else {
i = mid+1;
}
}
int FirsBig = j;
return lastSmo - FirsBig - 1;
}
}
0～n-1中缺失的数字
Easy 原题连接：0～n-1中缺失的数字
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。
示例：
输入: [0,1,3]
输出: 2
输入: [0,1,2,3,4,5,6,7,9]
输出: 8
提示：
- 1 <= 数组长度 <= 10000
解题思路
找到第一个nums[i] > i 的位置
Java代码
class Solution {
public int missingNumber(int[] nums) {
if(nums[0] > 0) return 0;
int i=0, j=nums.length-1;
for(;i<=j;) {
int mid = i+(j-i)>>1;
if(nums[mid] > mid) {
j = mid-1;
}else {
i = mid+1;
}
}
return i;
}
}
