详解数组刷题上
- 2019 年 10 月 6 日
- 筆記
详解数组刷题上
本专题内容如下：
一、初始定义及原地修改1.283. 移动零2.27. 移除元素3.26. 删除排序数组中的重复项4.80. 删除排序数组中的重复项 II二、基础思想应用1.75. 颜色分类2.88. 合并两个有序数组3.215. 数组中的第K个最大元素4.167. 两数之和 II – 输入有序数组5.209. 长度最小的子数组
一、初始定义及原地修改
类似题目：
- 283. 移动零
- 27. 移除元素
- 26. 删除排序数组中的重复项
注意的问题
- 如何定义变量？
- 如何从数组中删除？
- 剩余元素的排列是否要保证原有的相对顺序？
- 是否有空间复杂度的要求？ O(1)
1.283. 移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12] 输出: [1,3,12,0,0]
说明:
- 必须在原数组上操作，不能拷贝额外的数组。
- 尽量减少操作次数。
实现思路：
- 拿出非0元素
- 将非0元素拿出来，然后空位补0
实现：
循环一次找出不为0的index，并将该Index对应的值依次存储到数组中，后面的全部为0即可！
class Solution { public void moveZeroes(int[] nums) { int j=0; for(int i=0;i<nums.length;i++){ if(nums[i]!=0){ nums[j++]=nums[i]; } } //剩余位置放0 while(j<nums.length){ nums[j++]=0; } } }
2.27. 移除元素
给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1:
给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。
实现思路：
找到不等目标值的元素，然后利用不等目标值的个数原地修改数组。
实现：
class Solution { public int removeElement(int[] nums, int val) { int i,j=0; for(i=0;i<nums.length;i++){ if(nums[i]!=val){ nums[j++]=nums[i]; } } return j; } }
3.26. 删除排序数组中的重复项
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2], 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 你不需要考虑数组中超出新长度后面的元素。
实现思路：
找到当前元素与前一元素不等的位置，开始原地修改数组。
实现：
class Solution { public int removeDuplicates(int[] nums) { int i=1,j=0; while(i<nums.length){ if (nums[i]!=nums[i-1]){ nums[++j]=nums[i]; } i++; } return j+1; } }
4.80. 删除排序数组中的重复项 II
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定 nums = [1,1,1,2,2,3], 函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 你不需要考虑数组中超出新长度后面的元素。
实现思路：
1 2 cur back 1 2 2 pre cur back
当数组中的某一部分满足上述两者之一的时候，就可以移动cur(cur记录的就是该数组的实际大小)。
实现：
class Solution { public int removeDuplicates(int[] nums) { int cur,pre,back; cur=1; pre=cur-1; back=cur+1; while(back<nums.length){ if(nums[cur]!=nums[back]||(nums[cur]==nums[back] && nums[cur]!=nums[pre])){ pre=cur; nums[cur+1]=nums[back]; cur++; } back++; } return cur+1; } }
前面两个元素不修改，直到到第3个元素，也就是index=2开始比较。使用j来存储满足题意的位置，让nums[i]与nums[j-2]比较，然后赋值即可。
class Solution { public int removeDuplicates(int[] nums) { int i=2,j=2; while(i<nums.length){ if(nums[i]>nums[j-2]){ //这里一定是j-2而不是i-2，如果是i-2会在下面一行代码执行过程中将原来的值覆盖掉，此时结果就不对了，而如果是j-2，就是正确的，因为j中存放的就是未覆盖的值，如果所有元素都是不一样的，那么i与j的指向一致，而当元素并不一样的时候，j-2中就存放了i-2实际元素！ nums[j++]=nums[i]; } i++; } return j; } }
二、基础思想应用
基本思想：
- 快速排序
- 三路快排
- 二分查找
- 基数排序
类似题目：
- 75. 颜色分类
- 88. 合并两个有序数组
- 215. 数组中的第K个最大元素
- 167. 两数之和 II – 输入有序数组
- 209. 长度最小的子数组
二分查找法模板：
int l = 0, r = n-1; // 在[l...r]的范围里寻找target：前闭后闭 while( l <= r ){ // 只要还有可以查找的内容。当 l == r时,区间[l...r]依然是有效的 int mid = l + (r-l)/2; if( arr[mid] == target ) return mid; //mid已经判断过了 if( target > arr[mid] ) l = mid + 1; // target在[mid+1...r]中; [l...mid]一定没有target else // target < arr[mid] r = mid - 1; // target在[l...mid-1]中; [mid...r]一定没有target }
注意的问题
- 求mid值是采用(l+r)/2容易整形溢出
- 采用mid = l + (r-l)/2;
1.75. 颜色分类
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意: 不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0] 输出: [0,0,1,1,2,2]
实现思路：
统计一次红、白、黑的数量，然后再循环一次原地修改！
实现：
class Solution { public void sortColors(int[] nums) { int red=0,white=0,blue=0; for(int i=0;i<nums.length;i++){ switch (nums[i]){ case 0: red++; break; case 1: white++; break; default: blue++; } } for(int i=0;i<nums.length;i++){ if (i<red){ nums[i]=0; }else if(i<red+white){ nums[i]=1; }else{ nums[i]=2; } } } }
三路快排
class Solution { public void sortColors(int[] nums) { int red_white = -1; int white_blue= nums.length; int i=0; int temp; while(i<white_blue){ if(nums[i]==0){ red_white++; temp=nums[red_white]; nums[red_white]=nums[i]; nums[i]=temp; i++; }else if(nums[i]==2){ white_blue--; temp=nums[white_blue]; nums[white_blue]=nums[i]; nums[i]=temp; }else{ i++; } } } }
2.88. 合并两个有序数组
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
- 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
- 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:
输入: nums1 = [1,2,3,0,0,0], m = 3 nums2 = [2,5,6], n = 3 输出: [1,2,2,3,5,6]
实现思路：
从后往前遍历，然后去比较两数组大小，谁大先放谁。
实现：
class Solution { public void merge(int[] nums1, int m, int[] nums2, int n) { int n1=m-1,n2=n-1; for(int i=m+n-1;i>=0;i--){ if((n1>=0 && n2>=0 && nums1[n1]>=nums2[n2]) || (n2<0 && n1>=0)){ nums1[i]=nums1[n1]; n1--; }else if((n1>=0 && n2>=0 && nums1[n1]<nums2[n2]) || (n1<0 && n2>=0)){ nums1[i]=nums2[n2]; n2--; } } } }
3.215. 数组中的第K个最大元素
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2 输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4
说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
实现思路：
直接使用冒泡排序，当冒出k次后，此时的元素就是第K个最大元素。
实现：
class Solution { public int findKthLargest(int[] nums, int k) { int i,j; int n=nums.length; int temp; for (i=0;i<n-1;i++){ for (j=i+1;j<n;j++){ if (nums[i]<nums[j]) { temp=nums[i]; nums[i]=nums[j]; nums[j]=temp; } } k--; if(k==0){ break; } } return nums[i]; } }
交换多次快排
class Solution { public int findKthLargest(int[] nums, int k) { quickSort(nums,0,nums.length-1); return nums[k-1]; } public void quickSort(int[] nums,int left,int right){ if(left>right){ return; } int pivot = nums[left]; int i = left; int j = right; int temp; while(i<j){ while(i<j && nums[j]<=pivot) j--; if(i<j){ temp=nums[i]; nums[i]=nums[j]; nums[j]=temp; } while(i<j && nums[i]>=pivot) i++; if (i<j){ temp=nums[i]; nums[i]=nums[j]; nums[j]=temp; } } //nums[left]=nums[i]; 这种方法这行不能要！ nums[i]=pivot; quickSort(nums,left,i-1); quickSort(nums,i+1,right); } }
最后交换快排
class Solution { public int findKthLargest(int[] nums, int k) { quickSort(nums,0,nums.length-1); return nums[k-1]; } public void quickSort(int[] nums,int left,int right){ if(left>right){ return; } int pivot = nums[left]; int i = left; int j = right; int temp; while(i<j){ while(i<j && nums[j]<=pivot) j--; while(i<j && nums[i]>=pivot) i++; if (i<j){ temp=nums[i]; nums[i]=nums[j]; nums[j]=temp; } } nums[left]=nums[i]; //必须要！ nums[i]=pivot; quickSort(nums,left,i-1); quickSort(nums,i+1,right); } }
4.167. 两数之和 II – 输入有序数组
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。
说明:
- 返回的下标值（index1 和 index2）不是从零开始的。
- 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例:
输入: numbers = [2, 7, 11, 15], target = 9 输出: [1,2] 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
实现思路：
二分查找法
实现：
注意二分查找的代码中左右可以相等！
class Solution { public int[] twoSum(int[] numbers, int target) { int[] res=new int[2]; for(int i=0;i<numbers.length;i++){ int second = binarySearch(numbers, i+1, numbers.length-1, target-numbers[i]); if(second>-1){ res[0]=i+1; res[1]=second+1; } } return res; } public int binarySearch(int[] numbers, int start, int end, int target){ int i=start; int j=end; while(i<=j){ int mid=(i+j)/2; if(numbers[mid]== target){ return mid; }else if(numbers[mid]> target){ j=mid-1; }else{ i=mid+1; } } return -1; } }
5.209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
示例:
输入: s = 7, nums = [2,3,1,2,4,3] 输出: 2 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
进阶:
如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
实现思路：
循环+二分
实现：
注意二分查找的代码中左右可以相等！
时间复杂度：O(nlogn)，空间复杂度O(n)。
思路：
将原先数组所有数字累加求和得到一个新数组，例如：
nums=[2,3,1,2,4,3] parNums=[0,2,5,6,8,12,15]
然后循环parNums，对每一个数组中的index对应的值，利用二分法找到最小的窗口。
举个例子：
nums=[2,3,1,2,4,3] parNums=[0,2,5,6,8,12,15] -------------- i=0时 -------------- 第一轮 left=0,right=6 left<right,计算出mid=3，此时对应的值为6,mid距离i的和也就是6<7， 调整left=mid+1=4。 第二轮 left=4,right=6 left<right,计算出mid=5，此时对应的值为12，mid距离i的和也就是12>7， 调整right=mid-1。 是不是上述可以看作是查找7的二分法，那么后面依次类推即可。 当然left调整也可以是left++，right调整也可以是right--，也可以AC,但是效率会低一些！ -------------- ......
循环+二分
public class Solution { public int minSubArrayLen(int s, int[] nums) { int[] parNums = new int[nums.length+1]; for(int i=1;i<parNums.length;i++){ parNums[i]=parNums[i-1]+nums[i-1]; } int min=0; for(int i=0;i<parNums.length;i++){ int left=i; int right=parNums.length-1; while(left<=right){ int mid=left+(right-left)/2; int subSum=parNums[mid]-parNums[i]; if(subSum>=s){ right=mid-1; //可以换成right--; min=min==0?mid-i:Math.min(min,mid-i); }else{ left=mid+1; //可以换成left++; } } } return min; } }
