詳解數組刷題上
- 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; } }
