從邏輯結構而言，陣列是一種線性表；從存盤結構而言，一般認為，陣列占用一組連續的記憶體空間，來存盤一組具有相同型別的資料，因此，可以根據合法偏移量尋址，以隨機訪問陣列元素，下面介紹保持相對順序的陣列過濾器相關習題（一般要求只使用常數的額外空間），如同凈水器濾除雜質，演算法基本流程如下：
- 順序遍歷陣列元素
- 檢查是否符合條件
2.1 符合條件 -> 留下
2.2 不符合條件 -> 略過
遍歷讀取的程序，像是一個指標揮著衣袖，云彩依然在原地停留，“云彩”是（過濾前的）原始資料，雖然在訪問過一次之后就沒有利用價值了，但是它們依然無故地霸占著空間，白白地荒廢著空間，所以，為何不把這些空間重新利用起來，新陳代謝、變廢為寶呢？
要想達到這樣高效的空間利用率，自然還需要另一個覆寫更新指標，它表示“當下一個符合條件的元素出現時，應當填寫在哪個位置”，同時也作為計數器表示“當前已經維護好的，（過濾后的）新生資料的實際長度”，如果說讀指標的前行，是穩扎穩打、快馬加鞭，那么寫指標的進展，就依靠條件而相對緩慢，
因此，它們也被形象地稱為“快慢指標”，
??那就自己動手試試叭
??記得注意邊界條件哦
| 刷題清單 | 過濾條件 |
|---|---|
| 27.移除元素 | 等于目標值就不要，不等于目標值就要 |
| 26.洗掉有序陣列中的重復項 | 重復就不要，不重復就要 |
| 283.移動零 | 為零就不要，不為零就要 |
這兩題之所以不需要額外開辟臨時陣列，是因為其更新資料的覆寫進度總是比原始資料的訪問進度要慢（更準確的說是，覆寫進度不領先于讀取進度），進而不存在讀取臟資料導致結果紊亂與原始資料遺失的問題，
可是，88.合并兩個有序陣列這題，如果兩個讀指標、一個寫指標照常置于陣列頭部，將比較小的一方填入，倘若不使用額外空間，就可能發生沖突，舉例來說，此時此刻， \(nums_1\) 讀指標指向的原始資料是3，如果直接更新于 \(nums_1\) 上，那么寫指標就會領先讀指標，把還沒有訪問的資料“吞”掉，
怎么辦呢？觀察發現， \(nums_1\) 后方有許多空位，
倘若讀寫指標均倒序更新，寫指標將天然落后讀指標，
我們可以想象，即使\(nums1\)的??讀指標前期始終躺在原地，??寫指標也追不上，于是，我們就可以直接在陣列 \(nums_1\) 上原地修改，不需要額外空間！
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// 最新資料-寫指標
int now = m + n - 1;
// 原始資料-讀指標
int i = m - 1, j = n - 1;
// 條件：哪個更大填哪個，小的暫時先略過
while (i >= 0 && j >= 0) {
if (nums1[i] <= nums2[j]) {
nums1[now--] = nums2[j--];
} else {
nums1[now--] = nums1[i--];
}
}
// 某一個陣列觸碰邊界，另一個的元素直接掛載于尾部即可
// while (i >=0 ) nums1[now--] = nums1[i--];
while (j >= 0) nums1[now--] = nums2[j--];
}
}
對比來說，977.有序陣列的平方與上述習題有相似也有不同，
- 相似在于，非理想情況下陣列元素的絕對值符合“先遞減后遞增”的規律，仿佛就是兩個序列拼接而成的，
- 不同在于，原地修改無法保證覆寫更新進度和讀取訪問進度不沖突，需要新開辟一個陣列用于回傳答案，
class Solution {
public int[] sortedSquares(int[] nums) {
// 讀指標
int r1 = 0, r2 = nums.length - 1;
// 用于回傳答案
int[] ans = new int[r2 + 1];
// 倘若從讀指標的角度切入，應當為while(r1<=r2)
for (int w = r2; w >= 0; w--) {
if (Math.abs(nums[r2]) >= Math.abs(nums[r1])) {
ans[w] = nums[r2] * nums[r2];
r2--;
} else {
ans[w] = nums[r1] * nums[r1];
r1++;
}
}
return ans;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/543186.html
標籤：其他
上一篇：什么是計算機中的高速公路-總線？