详解数组刷题上
详解数组刷题上
详解数组刷题上
本专题内容如下：
一、初始定义及原地修改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;
}
}