Java中有关数组的知识：
2021.01.04 找出数组中重复的数字
今日题目：在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
- 思路：个人认为有两种解法。
- 法一：先对数组进行排序，可选时间复杂度较低的排序方式，例如：快速排序、归并排序等。然后从头开始遍历数组，若出现下一个数与上一个数相等，则表示出现了重复的情况。返回第一个遇到的重复的数。
- 法二：不用对数组进行排序，准备一个长度与目标数组长度相等的标记数组，然后从头遍历目标数组，每遇到一个数，就在标记数组对应的地方进行加1（标记数组初始化后每个元素的值为0，例：nums[2]=1,则进行++tag[1]的操作）；最后，遍历一遍标记数组，遇到的第一个元素值大于1的即为重复出现的数字。
- 法三（力扣给的官方解法）：利用哈希集合的特性（集合中无重复值），所以在往集合中添加值的时候，若出现重复值，则会返回false表示添加失败。
- 法四（大佬题解）：原地置换。一个萝卜一个坑的思路，数组下标为 i 的数组元素对应的值应为 i ；从头开始遍历，若第i个数字为m，先判断第i位数字是否与第m位数字相等，若相等，则表示有重复的值，否则将第m个数字与第i个数字对换，即第m位上的数字为m。交换之后若第i位上的数字仍不为i，则继续交换，若第i位上的数字为i，则对下一位数字进行相同的操作。
- 法五（剑指里边的另一种解法）：把从1～n的数字从中间的数字m分为两部分,前面一半为1～m,后面一半为m+1~n。如果1~m的数字的数目超过m，那么这一半的区间里一定包含重复的数字;否则，另一半m+1～n的区间里一定包含重复的数字。我们可以继续把包含重复数字的区间一分为二，直到找到一个重复的数字。这个过程和二分查找算法很类似，只是多了一步统计区间里数字的数目。时间复杂度O(nlogn)（神奇）（有缺陷）
- 自己的菜鸡代码：
```java
//法二的代码
class Solution {
public int findRepeatNumber(int[] nums) {
} }int tag[] = new int[nums.length];for(int i = 0; i < nums.length; i++)++tag[nums[i]];for(int i = 0; i < nums.length; i++)if(tag[i] > 1)return i;//若是没有重复的值则返回-1return -1;
//法一的代码========================================================= class Solution { public int findRepeatNumber(int[] nums) { QuickSort(nums,0,nums.length-1); int i; for(i = 0;i < nums.length-1; i++){ if(nums[i] == nums[i+1]) break; } return nums[i]; }
public void QuickSort(int[] nums,int head,int rear){//进行快速排序，获得已排好序的数组if(head < rear){int part = partition(nums,head,rear);QuickSort(nums,head,part-1);QuickSort(nums,part+1,rear);}}public int partition(int[] nums,int head,int rear){int tag = nums[head];while(head < rear){while(nums[rear]>=tag && head<rear) --rear;nums[head] = nums[rear];while(nums[head]<=tag && head<rear) ++head;nums[rear] = nums[head];}nums[head] = tag;return head;}
}
//法三的代码=======================================================
class Solution {
public int findRepeatNumber(int[] nums) {
Set
return tag;}
}
//法四的代码======================================================= class Solution { public int findRepeatNumber(int[] nums) { int temp; for(int i = 0; i<nums.length; i++){ while(nums[i] != i){ if(nums[i] == nums[nums[i]]){ return nums[i]; }
temp = nums[i];nums[i] = nums[temp];nums[temp] = temp;}}return -1;}
}
法二的运行结果（左）：法二的时间复杂度为O(n)，但是空间复杂度也为O(n)，是采取空间换时间的方式。<br />法一的运行结果（右）：啊，可能是哪里出错了<br /><br />法三的运行结果（左）：遍历数组一遍的时间复杂度为O(n)，添加元素的时间复杂度为O(1)，故总的时间复杂度为O(n)，但是用了一个额外的哈希集合，故空间复杂度为O(n)。<br />法四的运行结果（右）：<br /><a name="zscBO"></a>### 2021.01.05 二维数组中的查找今日题目：在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。- 思路：个人感觉这个应该有多种解决方法1. 法一：暴力法解决，逐行遍历查找，时间复杂度为O(n*m)。若n与m是很大的数字则时间复杂度会很高，而且没有利用题干中给出的递增条件1. 法二：因为每一行都按照从左到右递增的顺序排序，所以可以对该二维数组逐行进行二分查找。一行的二分查找时间为O(logm)，则整个的时间复杂度为O(nlogm)。1. 法三（看评论区）：线性查找，利用题干中给出的条件，即每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序，所以从右上角开始，若大于目标值，则往下一行，若小于目标值，则往前一列。评论区有个大佬给了张图，我觉得非常清楚明白。如下图，时间复杂度为O(n+m)。。- 自己的菜鸡代码：```java//法一的代码class Solution {public boolean findNumberIn2DArray(int[][] matrix, int target) {if(matrix.length < 1) return false;int row = matrix.length;int colunm = matrix[0].length;int i,j;for(i = 0; i < row; i++){for(j = 0; j < colunm; j++){if(matrix[i][j] == target){return true;}}}return false;}}// 法二的代码class Solution {public boolean findNumberIn2DArray(int[][] matrix, int target) {if(matrix.length < 1) return false;int row = matrix.length;int colunm = matrix[0].length;int head,rear,mid;for(int i = 0; i < row; i++){head = 0;rear = colunm - 1;while(head <= rear){mid = (head + rear) / 2;if(matrix[i][mid] == target) return true;else if(matrix[i][mid] < target) head = mid + 1;else rear = mid - 1;}}return false;}}// 法三的代码class Solution {public boolean findNumberIn2DArray(int[][] matrix, int target) {//线性查找的方法if(matrix.length < 1) return false;int row = matrix.length;int colunm = matrix[0].length;int i = 0, j = colunm - 1;while(i >= 0 && i < row && j >= 0 && j < colunm){if(matrix[i][j] == target) return true;else if(matrix[i][j] < target) ++i;else --j;}return false;}}
法一的运行结果（左）：
法三的运行结果（右）：
可能是因为测试用例的范围为0 <= n <= 1000，0 <= m <= 1000
故以下两个结果不明显，若n与m的值特别大，则法三的时间消耗会明显更少一些。
法二的运行结果：
2021.01.19 在排序数组中查找数字
今日题目：统计一个数字在排序数组中出现的次数。
提示：0 <= 数组长度 <= 50000
- 思路：
- 法一：暴力美学。整个数组遍历一遍，但是这样就没有用到“排序数组”这一特点。时间复杂度为O(n)，空间复杂度为O(1)。
- 法二：利用“排序数组”这一特点，这题是二分查找的变形。先查找右边界，若数组中不包含target则提前返回0；若数组中包含target，则在[0, j]中一定包含左边界，故再用一次二分查找。时间复杂度为O(logn)，空间复杂度为O(1)。
- 自己的菜鸡代码：
```java
// 法一
class Solution {
public int search(int[] nums, int target) {
} }int count = 0;for(int i = 0; i < nums.length; i++){if(nums[i] == target) ++count;}return count;
// 把法一稍稍改了一下，就快了许多 class Solution { public int search(int[] nums, int target) { int count = 0; for(int i = 0; i < nums.length; i++){ if(nums[i] < target) continue; else if(nums[i] == target) ++count; else break; } return count; } }
// 法二 class Solution { public int search(int[] nums, int target) { if(nums.length == 0) return 0; int i = 0, j = nums.length - 1; // 查找y右边界 int mid; while(i <= j){ mid = (i + j) / 2; if(nums[mid] <= target) i = mid + 1; if(nums[mid] > target) j = mid - 1; } // 判断是否包含target，若不包含则提前结束，若包含则继续查找左边界 if(j < 0 || nums[j] != target) return 0; // 查找左边界 int right = j; i = 0; while(i <= j){ mid = (i + j) / 2; if(nums[mid] < target) i = mid + 1; if(nums[mid] >= target) j = mid - 1; }
return right - i + 1;}
}
- 运行结果：法一<br /><br />法二<br /><a name="pZYRw"></a>### 2021.01.19 和为 s 的两个数字今日题目：输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。<br /><br />**限制：**- 1 <= nums.length <= 10^5- 1 <= nums[i] <= 10^6- 思路：- 法一：暴力美学。逐个比对，没什么技术含量，时间复杂度为O(n)，空间复杂度为O(1)，giao超出时间限制 （理智丧失.jpg）这个不配叫算法😊。想到一个时间复杂度应该会低一点的，第一个数也是逐个尝试，时间复杂度为O(n)，第二个数在第一个数后面的区间内采用二分查找法O(logn)。- 法二：用一个哈希表，通过遍历数组找到数字组合，时间复杂度和空间复杂度都为O(n)。- 法三：双指针碰撞（看评论区的大佬解法）。head从下标0开始，tail从 nums.length-1 开始，在head < tail 的循环条件下，若是nums[head] + nums[tail] > target ，则tail减一；若是nums[head] + nums[tail] < target ，则head加一若是相等，则返回nums[head] 、 nums[tail] 。若不存在则返回空数组。这样子时间复杂度为O(n)，空间复杂度为O(1)。- 自己的菜鸡代码：```java// 法一 （超出时间限制55555不可取）class Solution {public int[] twoSum(int[] nums, int target) {// 暴力美学int temp;int[] result = new int[2];for(int i = 0; i < nums.length && nums[i] < target; i++){temp = target - nums[i];for(int j = i + 1; j < nums.length && nums[j] < target; j++){if(nums[j] == temp){result[0] = nums[i];result[1] = nums[j];return result;}if(nums[j] + nums[i] > target) break;}}return null;}}// 法一改进版class Solution {public int[] twoSum(int[] nums, int target) {int temp;int[] result = new int[2];for(int i = 0; i < nums.length; i++){temp = target - nums[i];int left = i + 1, right = nums.length - 1, mid;while(left <= right){mid = (left + right) / 2;if(nums[mid] < temp) left = mid + 1;else if(nums[mid] > temp) right = mid - 1;else{result[0] = nums[i];result[1] = nums[mid];return result;}}}return null;}}// 法二 利用哈希表class Solution {public int[] twoSum(int[] nums, int target) {// 利用哈希表降低时间复杂度HashSet<Integer> set = new HashSet<>();int i;for(int num : nums){set.add(num);}for(int num : nums){int temp = target - num;if(set.contains(temp)){return new int[]{num, temp};}}return new int[]{};}}// 法三class Solution {public int[] twoSum(int[] nums, int target) {// 双指针碰撞int head = 0, tail = nums.length - 1;while(head < tail){int temp = nums[head] + nums[tail];if(temp > target) --tail;else if(temp < target) ++head;else return new int[]{nums[head], nums[tail]};}return new int[]{};}}
- 运行结果：
法一改进前（左）和改进后（右）
法二（左）、法三（右）
2021.01.19 旋转数组的最小数字
今日题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。
- 思路：
- 法一：遍历数组，将当前值域后面一个值相比较，若是前一个数大于后一个数，则后一个数即旋转数组中的最小数字。若是遍历完整个数组都没有发现这样子的一对数，则表示该数组是从小到大排列，因此最小值即为第一个数组元素。时间复杂度为O(n)，空间复杂度为O(1)。
- 法二：采用二分查找法。时间复杂度为O(logn)，空间复杂度为O(1)。看大佬的思路有点不好理解。寻找旋转数组的最小元素即为寻找右排序数组的首个元素nums[x]，称 x 为旋转点。
- 初始化：i 指向数组首部，j 指向数组尾部。
- 循环二分：设mid =（i + j）/ 2（可以分成三种情况）
- 当nums[mid] < nums[j]，旋转点在[i , m]中。
- 当nums[mid] > nums[j]，旋转点在[m + 1 , j]中。
- 当nums[mid] == nums[j]，旋转点的位置不好确定，此时可将 j 进行减一处理以缩小判断范围。
- 为什么要进行 —j的操作呢？
因为在出现nums[mid] == nums[j]时，有两种情况。举例[1,0,1,1,1,1,1,1]和[1,1,1,1,1,0,1,1]
- 当x < j时：易得执行j = j - 1后旋转点 x 仍在区间[i , j]内。- 当x = j时：执行j = j - 1后越过（丢失）了旋转点 x ，但最终返回的元素值nums[i]仍等于旋转点值nums[x]。
======以下这一段不好理解======
- 由于x = j，因此nums[x] = nums[j] = nums[mid] <= nums[i]；- 又由于i <= m < j，恒成立，因此有m < x，即此时 m 一定在左排序数组中，因此nums[m] >= nums[i]；- - 可推出 nums[i] = nums[m]，且区间 [i, m] 内所有元素值相等，即有：nums[i]=nums[i+1]=⋯=nums[m]=nums[x]。此时，执行 j = j - 1 后虽然丢失了旋转点 x ，但之后区间 [i, j] 只包含左排序数组，二分下去返回的一定是本轮的 nums[i] ，而其与 nums[x] 相等。- 为什么本题二分法不用 nums[m] 和 nums[i] 作比较？- 二分目的是判断 m 在哪个排序数组中，从而缩小区间。而在 nums[m] > nums[i]情况下，无法判断 m 在哪个排序数组中。本质上是由于 j 初始值肯定在右排序数组中； i 初始值无法确定在哪个排序数组中。举例如下：- 对于以下两示例，当 i = 0, j = 4, m = 2 时，有 nums[m] > nums[i] ，而结果不同。- [1, 2, 3, 4 ,5] 旋转点 x = 0 ： m 在右排序数组（此示例只有右排序数组）；- [3, 4, 5, 1 ,2] 旋转点 x = 3 ： m 在左排序数组。
- 自己的菜鸡代码：
```java
// 法一
class Solution {
public int minArray(int[] numbers) {
} }int i;for(i = 0; i < numbers.length - 1; i++){if(numbers[i] > numbers[i+1]) break;}if(i == numbers.length - 1) return numbers[0];return numbers[i+1];
// 法二 代码很短但是很神奇 class Solution { public int minArray(int[] numbers) { int i = 0, j = numbers.length - 1, mid; while(i < j){ mid = (i + j) / 2; if(numbers[mid] < numbers[j]) j = mid; else if(numbers[mid] > numbers[j]) i = mid + 1; else —j; } return numbers[i]; } }
- 运行代码：法一（左，虽然看上去好像还行的样子，但是一旦数量级上来了，暴力法是最差的，所以还是老老实实学习怎么写算法8），法二（右）<br /><a name="hZTfE"></a>### 2021.01.22 打印从1到最大的n位数今日题目：输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。<br />- 思路：因为是十进制数，所以求出打印上限为（10^n）,但是java中的指数运算是Math.pow(a, b)；返回的值为double类型，需要强制转为int类型即可，这题返回的是int[]数组，说明不会用int类型不会溢出，否则最好用long类型。> 本题在面试中通常是要考虑大数问题，在大数问题中必须用字符串来模拟整型数据的加法，若直接用整型数据的话，会产生溢出。- 自己的菜鸡代码：```javaclass Solution {public int[] printNumbers(int n) {int num = (int)Math.pow(10,n);int[] res = new int[num - 1];for(int i = 1; i < num; i++){res[i - 1] = i;}return res;}}
- 运行结果：
2021.01.22 数组中出现次数超过一半的数字
今日题目：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素。
限制：1 <= 数组长度 <= 50000
- 思路：
- 法一：利用哈希表来记录所有值的出现次数，若有值的出现次数大于数组长度的一半，就直接返回该值。时间复杂度为O(n)，空间复杂度为O(n)，本来想用时间换空间的，结果效果好像很一般。时间复杂度为O(n)，空间复杂度为O(n)。
- 法二：可以将数组进行快速排序，然后中位数就是出现次数超过一半的数字。时间复杂度为O(nlogn)，空间复杂度为O(1)。
- 法三：（在评论区学到的一个新玩意）摩尔投票法：若记众数的票数为-1，则一定右所有数字的票数和>0；若数组的前a个数字的票数和=0，则数组剩余（n-a）个数字的票数和一定仍>0，记（n - a）个数字的中枢仍为x。当发生 票数和 = 0=0 时，剩余数组的众数一定不变。
- 算法流程：
- 初始化：票数统计vote = 0，众数设为x。
- 循环：遍历数组nums中的每个数字num。
- 算法流程：
当票数vote = 0，则假设当前数字num是众数。
当num = x，票数vote+1；当num！= x，票数vote-1.
- 返回值：返回x即可。- 若数组中不一定包含众数，则最后再遍历一遍数组，统计x的数量，若大于数组长度的一半，则返回x，否则未找到众数。- 时间复杂度为O(n)，空间复杂度为O(1)。
- 自己的菜鸡代码：
```java
// 法一
class Solution {
//private int[] data;
public int majorityElement(int[] nums) {
} }// 用空间换时间HashMap<Integer,Integer> map = new HashMap<>();int num = 0;for(int i = 0; i < nums.length; i++){if(map.get(nums[i]) == null){num = 1;}else {num = map.get(nums[i]);++num;}if(num > nums.length / 2) return nums[i];map.put(nums[i], num);}// forreturn num;
// 法二 class Solution { //private int[] data; public int majorityElement(int[] nums) { nums = QuickSort(nums, 0, nums.length - 1); return nums[nums.length / 2]; }
int[] QuickSort(int[] data, int head, int rear){if(head > rear) return data;int left = head, right = rear;int flag = data[head];while(head < rear){while(head < rear && data[rear] >= flag) --rear;data[head] = data[rear];while(head < rear && data[head] <= flag) ++head;data[rear] = data[head];}data[head] = flag;QuickSort(data, left, head - 1);QuickSort(data, head + 1, right);return data;}
}
// 法三 （太秀了） class Solution { //private int[] data; public int majorityElement(int[] nums) { // 摩尔投票法 int x = 0, vote = 0; for(int num: nums){ if(vote == 0) x = num; vote += num==x ? 1:-1; } return x; } }
- 运行结果：法一（左）、法二（右）<br /><br />法三：<br /><a name="E6we9"></a>### 2021.01.25 调整数组顺序使奇数位于偶数前面今日题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。<br /><br />提示：1. 1 <= nums.length <= 500001. 1 <= nums[i] <= 10000- 思路：采用双指针的方式，设头指针为head，尾指针为rear，在head<rear的情况下，head从前往后移动，遇到偶数停下，rear从后往前移动，遇到奇数停下，交换num[head]与num[rear]。- 自己的菜鸡代码：```javaclass Solution {public int[] exchange(int[] nums) {int head = 0, rear = nums.length - 1;while(head < rear){while(head < rear && nums[head] % 2 == 1) ++head;while(head < rear && nums[rear] % 2 == 0) --rear;int temp = nums[head];nums[head] = nums[rear];nums[rear] = temp;}return nums;}}
- 运行结果：
2021.01.25 顺时针打印矩阵（未写）
今日题目：输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
限制：
- 0 <= matrix.length <= 100
0 <= matrix[i].length <= 100
思路：
- 自己的菜鸡代码：
- 运行结果：
2021.01.25 最小的k个数
今日题目：输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
限制：
- 0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000
思路：
法一：可以先将数组进行快速排序，然后取前k个不重复的数。时间复杂度为O(nlogn)，空间复杂度为O(1)。
看评论区发现不需要对整个数组进行快速排序，当锚点位置在第k个，则前面的数都是小于锚点值的，故直接返回前k个数就好。
法二：可以利用一个辅助数组tag，因为0 <= arr[i] <= 10000，所以可以遍历arr数组，经历每个数组时就进行++tag[arr[i]]的操作，最后遍历tag数组，前k个tag[i] > 0 的元素即为所求结果。时间复杂度为O(n)，空间复杂度为O(n)。
法三：可以用堆（俺暂时不会）。
自己的菜鸡代码： ```java // 法一 class Solution { //private int[] nums; public int[] getLeastNumbers(int[] arr, int k) {
// 先排序再取值if(arr.length == 0 || k == 0) return new int[]{};int[] res = new int[k];arr = QuickSort(arr, 0, arr.length - 1);res[0] = arr[0];int count = 1;for(int i = 1; i < arr.length; i++){if(count == k)return res;res[count++] = arr[i];}return res;
}
int[] QuickSort(int[] nums, int head, int rear){
if(head >= rear) return nums;int left = head, right = rear;int flag = nums[head];while(head < rear){while(head < rear && nums[rear] >= flag) --rear;nums[head] = nums[rear];while(head < rear && nums[head] <= flag) ++head;nums[rear] = nums[head];}nums[head] = flag;QuickSort(nums, left, head - 1);QuickSort(nums, head + 1, right);return nums;
} }
// 法一改进版 class Solution { public int[] getLeastNumbers(int[] arr, int k) { // 先排序再取值 if(arr.length == 0 || k == 0) return new int[]{}; return QuickSort(arr, 0, arr.length - 1, k); }
int[] QuickSort(int[] nums, int head, int rear, int k){int index = partition(nums, head, rear);if(head == k - 1) return Arrays.copyOf(nums, k);return index >= k? QuickSort(nums, head, index - 1, k):QuickSort(nums, index + 1, rear, k);}int partition(int[] nums, int head, int rear){int left = head, right = rear;int flag = nums[head];while(head < rear){while(head < rear && nums[rear] >= flag) --rear;nums[head] = nums[rear];while(head < rear && nums[head] <= flag) ++head;nums[rear] = nums[head];}return head;}
}
// 法二 使用额外的辅助空间 class Solution { //private int[] nums; public int[] getLeastNumbers(int[] arr, int k) { if(arr.length == 0 || k == 0) return new int[]{}; int[] tag = new int[10000+1]; for(int i = 0; i < arr.length; i++){ ++tag[arr[i]]; } int[] res = new int[k]; int count = 0; for(int i = 0; i < tag.length; i++){ if(tag[i] > 0){ for(int j = 0; j < tag[i] && count < k; j++) res[count++] = i; } if(count == k) return res; } return res; } }
- 运行结果：法一（图一）、法二（图二）、法一改进版（图三）<br /><a name="loEoJ"></a>### 2021.01.27 0~n-1中缺失的数字今日题目：一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。<br /><br />限制：1 <= 数组长度 <= 10000- 思路：> 排序数组中的搜索问题首先想到二分查找，或者是双指针法- 法一：想到之前的一个原地排序的算法，这题是否能参考一下，分为两种情况：一种是数组中有n-1，另一种情况是缺失的数就是n-1，进行原地排序后，再遍历一遍数组，n-1所在的位置就是缺失的数，若是没有查找到n-1，则直接返回n-1。原地排序的过程：若nums[i] != i 且nums[i] != n -1，就互换nums[i]与nums[ nums[i] ]的值。时间复杂度为O(n)，空间复杂度为O(1)。- 法二：二分查找。我忽略了题目中一个很重要的条件：这是个递增排序的数组。根据题意，数组按照以下规则划分为两部分：左子数组：nums[i] = i ，右子数组：nums[i] != i ，因此，缺失的数就是右子数组首元素的索引值。- 算法过程：1. 初始化：i = 0；j = nums.length；1. 循环二分：当i <= j时循环；1. 计算中点mid = （i + j）/ 2；1. 若num[i] == i，则右子数组首元素一定在区间[mid + 1, j]中；1. 若nums[i] != i，则右子数组首元素一定在区间[i , mid - 1]中；3. 返回值：跳出循环时，变量i和j分别指向“右子数组首元素”和“左子数组末元素”。返回i即可。- 时间复杂度：O(logn)，空间复杂度O(1)；- 法三：因为之前忽略了数组是递增的这个条件，所以这个方法就直接遍历数组，当遇到数组索引和对应的值不同时，就直接返回索引值 i 。- 时间复杂度：O(n)，空间复杂度：O(1)。- 自己的菜鸡代码：```java// 法一class Solution {public int missingNumber(int[] nums) {int temp;for(int i = 0; i < nums.length; i++){while(nums[i] != i && nums[i] != nums.length){temp = nums[i];nums[i] = nums[temp];nums[temp] = temp;}}for(int i = 0; i < nums.length; i++){if(nums[i] == nums.length) return i;}return nums.length;}}// 法二class Solution {public int missingNumber(int[] nums) {// 采用二分查找的思想（这个要怎么写啊555好难）int i = 0, j = nums.length - 1, mid;while(i <= j){mid = (i + j) / 2;if(nums[mid] == mid) i = mid + 1;else j = mid - 1;}return i;}}// 法三class Solution {public int missingNumber(int[] nums) {int i;for(i = 0; i < nums.length; i++){if(nums[i] != i) return i;}return i;}}
- 运行结果：
法一（1），法二（2），法三（3）：
2021.01.28 寻找数组的中心索引
今日题目：给定一个整数类型的数组 nums，请编写一个能够返回数组 “中心索引” 的方法。
我们是这样定义数组 中心索引 的：数组中心索引的左侧所有元素相加的和等于右侧所有元素相加的和。
如果数组不存在中心索引，那么我们应该返回 -1。如果数组有多个中心索引，那么我们应该返回最靠近左边的那一个。
说明：
- nums 的长度范围为 [0, 10000]。
任何一个 nums[i] 将会是一个范围在 [-1000, 1000]的整数。
思路：
- 法一：暴力法。遍历一遍数组，逐个计算左侧元素和右侧元素相加的值，若存在，则返回分界点的索引值，若不存在则返回-1。时间复杂度为O(n)，空间复杂度为O(1)。
- 法二：是根据提示写出来的555我好菜。设置一个辅助数组value，长度为nums.length+1，value[i]用来保存nums[0] + nums[1] + ……+nums[i-1]的结果。
- value[0] = 0：nums[0]的左子数组和为0；value[1] = nums[0]：nums[1]的左子数组和 = nums[0]，value[nums.length] = nums[0] + ……+ nums[nums.length - 1]：nums[i]整个数组之和。
- 然后遍历value数组，value[i]代表nums[i]的左子数组之和，value[nums.length] - value[i] - nums[i]代表右子数组之和。所以当存在左子数组之和等于右子数组之和的情况时，直接返回索引值 i 。
自己的菜鸡代码： ```java // 法一 class Solution { public int pivotIndex(int[] nums) {
// 暴力法int left, right;for(int i = 0; i < nums.length; i++){left = 0; right = 0;for(int j = 0; j < i; j++) left += nums[j];for(int k = i + 1; k < nums.length; k++) right += nums[k];if(left == right) return i;}return -1;
} }
// 法二 class Solution { public int pivotIndex(int[] nums) { int[] value = new int[nums.length+1]; for(int i = 1; i <= nums.length; i++){ value[i] = value[i-1] + nums[i - 1]; }
for(int i = 0; i < nums.length; i++){if(value[nums.length] - value[i] - nums[i] == value[i]) return i;}return -1;}
}
- 运行结果：法一（左）、法二（右）：<br /><a name="Ntnhf"></a>### 2021.01.28 和为S的连续正数序列（未写）今日题目：输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。<br /><br />限制：1 <= target <= 10^5- 思路：- 自己的菜鸡代码：- 运行结果：<a name="qBGS1"></a>### 2021.01.30 数组中数字出现的次数（位运算牛哇）今日题目：一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。<br /><br />限制：2 <= nums.length <= 10000- 思路：（5555想不出来）看评论区官方给出的解法是用异或，因为有两个只出现过一次的数字，其他数字都出现了两次，所以有两种情况：将整个数组分成左右子数组，两个数字在不同的子数组中，两个数都在同一子数组中。> 查找只出现一次的数字（1个）：全员进行异或操作即可。考虑异或操作的性质：对于两个操作数的每一位，相同结果为 0，不同结果为 1。那么在计算过程中，成对出现的数字的所有位会两两抵消为 0，最终得到的结果就是那个出现了一次的数字。算法：<br />先把整个数组进行异或，最后得到的数字就是两个目标值异或的结果（肯定不为0），找到最低位的1，然后以这一位为分组依据。再将这两组内的元素进行异或，最后得出的两个结果就是所求值。- 自己的菜鸡代码：```javaclass Solution {public int[] singleNumbers(int[] nums) {int ret = 0;for (int n : nums) {ret ^= n;}int div = 1;while ((div & ret) == 0) {div <<= 1;}// 下面的比较不好理解int a = 0, b = 0;for (int n : nums) {if ((div & n) != 0) {a ^= n;} else {b ^= n;}}return new int[]{a, b};}}
- 运行结果：
2021.01.31 数组中数字出现的次数II（同样是位运算）
今日题目：在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
限制：
- 1 <= nums.length <= 10000
1 <= nums[i] < 2^31
思路：
- 法一：以空间换时间，可以用哈希表记录每个数字出现的次数，最后遍历一遍哈希表找到次数为1的目标值返回即可。时间复杂度：O(n)，空间复杂度(n)。（大佬甚至没有列出这种方法orz）。（大佬们总能玩出新花样）
- 法二：因为只有一个数字出现了一次，其他数字出现了三次，所以可以利用一个辅助的数组rec（容量为32位）用于记录每一位1出现的次数，最后遍历rec数组，都每个值都进行模3计算，若是结果为0，则代表目标值的这一位为0，若结果为1，则表示目标值的这一位为1。
- 法三：（有限状态自动机，大佬牛哇）看不懂。
- 自己的菜鸡代码：
```java
// 法一 哈希表法
class Solution {
public int singleNumber(int[] nums) {
} }// 没有时间跟空间的要求，所以可以采用哈希表Map<Integer,Integer> map = new HashMap<>();int temp = 0;for(int i = 0; i < nums.length; i++){if(map.get(nums[i]) == null) map.put(nums[i],1);else {temp = map.get(nums[i]);map.put(nums[i], ++temp);}}for (Map.Entry<Integer, Integer> entry : map.entrySet()) {if(entry.getValue() == 1){temp = entry.getKey();break;}}return temp;
// 法二 统计二进制数中1的数量 class Solution { public int singleNumber(int[] nums) { int res = 0; int[] rec = new int[32]; for(int num : nums){ for(int i = 31; i >= 0; —i){ // 少点if判断能降低时间复杂度 rec[i] += (num & 1); num >>>= 1; } } for(int i = 0; i < 32; i++){ res <<= 1; res |= (rec[i] % 3); } return res; } }
```
- 运行结果：
法一（1）、法二（2）、法三（3）
2021.02.12 杨辉三角
今日题目：给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。在杨辉三角中，每个数是它左上方和右上方的数的和。
进阶：你可以优化你的算法到 O(k) 空间复杂度吗？
- 思路：
- 自己的菜鸡代码：
- 运行结果：
若有收获，就点个赞吧
0 人点赞
