Day04_剑指Offer
得到一点小启发，顺序的就会想到二分 树的就想到递归 倒序的就想到栈。
通过每天做做题，第二天重新思考前一天学的算法题，每天都有进步。加油
分享一句话：路都是一步一个脚印走出来的，没有人可以突然暴富，只有厚积薄发才能走得更远。加油！！
今天的三道题都用到二分法
package com.sorrymaker.day2804;
import org.junit.Test;
/**
* 找出一个长度为n数组nums里面的 重复数字，只要重复了就拿出来。
*
* 在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。
* 数组中某些数字是重复的，但不知道有几个数字重复了，
* 也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
* @Author nextGame
* @Date 2021/8/15 15:32
* @Version 1.0
*/
public class findRepeatNumber {
@Test
public void test(){
int[] nums ={3, 4, 2, 1, 0, 1};
System.out.println(findRepeatNumber(nums));
}
public int findRepeatNumber(int[] nums) {
//这个是索引，从0，开始
int i = 0;
while(i < nums.length) {
//假如数组中的数据nums[i] == i ; 即是nums[1] = 1的时候
if(nums[i] == i) {
//索引加1，继续遍历循环。因为true的话，说明，现在的索引和对应的值是对应的。
i++;
continue;
}
//这里就要拆封一下了。我们首先来看，
//当nums[i] = i ; nums[num[i]] ==>> nums[i] == nums[i]这里就会成立。
//为什么这里会返回呢？因为我们上面的if语句已经判断过了，假如索引 == num[i] ,我们就会i++，并继续循环。
// 即是出现重复的值，我们就返回这个值出来。
//因为索引是从0开始的
if(nums[nums[i]] == nums[i]) {
return nums[i];
}
//这里下面就是帮助我们排序数组把，把
//存放nums数组 的 i索引的数字。
int tmp = nums[i];
//将nums索引位temp 的数值 赋值给 nums 索引为 i的 。
nums[i] = nums[tmp];
//这里就是把对应位置的num[tmp] = tmp
nums[tmp] = tmp;
}
return -1;
}
}
/**
* 太慢太垃圾了，更新一个又快又猛的。
* int count=0;
* for (int i = 0; i < nums.length; i++) {
* for (int j = i+1;j<nums.length;j++){
* if(nums[i] == nums[j]){
* return count = nums[j];
* }
*
* }
* }
* return count;
*/
package com.sorrymaker.day2804;
/**
* 排序数组中的搜索问题，首先想到 二分法 解决
* @Author nextGame
* @Date 2021/8/15 17:28
* @Version 1.0
*/
public class MissingNumber {
public int missingNumber(int[] nums) {
//左边界 i ，右边界 j
int i = 0, j = nums.length - 1;
while (i <= j) {
//二分法
int m = (i + j) / 2;
if (nums[m] == m) {
i = m + 1;
} else {
j = m - 1;
}
}
return i;
}
}
package com.sorrymaker.day2804;
import org.junit.Test;
/**
* 排序数组记得用二分法，记得用二分法，记得，记得噢噢噢噢
* 二分法，就是找到想要找到的数字的左边和右边，右边-左边-1就是target出现的频率了。
* 这道题用的是优化的二分法，由于是排序数组，只需要找到有边界，和target-1的右边界，就是出现的次数了。
* 例如 target = 8， target-1 = 7 。 target的右边界为9，target-1 的有边界为8，
* 然后重复次数 = target右边界 - target-1的右边界 。
* @Author nextGame
* @Date 2021/8/15 16:42
* @Version 1.0
*/
public class Search {
@Test
public void test() {
int[] nums = {10, 11, 12, 13, 14, 15};
int target = 10;
System.out.println(search(nums, target));
}
public int search(int[] nums, int target) {
return count(nums,target)-count(nums,target-1);
}
int count(int[] nums, int target) {
//i 和 j分别是数组的起始索引和结尾索引。
int i = 0, j = nums.length - 1;
//这里的i和j分别是左右边界，左边始终小于等于右边
while(i <= j) {
// 二分得到的值。
int m = (i + j) / 2;
//当数组在m索引的值 <=目标值，说明，左边还可以在缩小一格，即i= m+1
if(nums[m] <= target) {
i = m + 1;
} else {
//当出先数组在m索引的值 >目标值，说明，右边可以在缩小一点，即j=m-1。
j = m - 1;
}
}
return i;
}
}
/**
* 弱智写法
* int count=0;
* for(int n:nums){
* if(n==target){
* count++;
* }
* }
* return count;
* }
*/