面試 TOP150 數(shù)組系列
LC169. 多數(shù)元素與 Boyer–Moore 投票算法
LC27. 移除元素 remove-element
給你一個數(shù)組 nums 和一個值 val，你需要 原地 移除所有數(shù)值等于 val 的元素。元素的順序可能發(fā)生改變。然后返回 nums 中與 val 不同的元素的數(shù)量。
假設 nums 中不等于 val 的元素數(shù)量為 k，要通過此題，您需要執(zhí)行以下操作：
更改 nums 數(shù)組，使 nums 的前 k 個元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。
用戶評測：
評測機將使用以下代碼測試您的解決方案：
int[] nums = [...]; // 輸入數(shù)組
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 長度正確的預期答案。
// 它以不等于 val 的值排序。
int k = removeElement(nums, val); // 調(diào)用你的實現(xiàn)
assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 個元素
for (int i = 0; i < actualLength; i++) {
assert nums[i] == expectedNums[i];
}
如果所有的斷言都通過，你的解決方案將會 通過。
示例 1：
輸入：nums = [3,2,2,3], val = 3
輸出：2, nums = [2,2,,]
解釋：你的函數(shù)函數(shù)應該返回 k = 2, 并且 nums 中的前兩個元素均為 2。
你在返回的 k 個元素之外留下了什么并不重要（因此它們并不計入評測）。
示例 2：
輸入：nums = [0,1,2,2,3,0,4,2], val = 2
輸出：5, nums = [0,1,4,0,3,,,_]
解釋：你的函數(shù)應該返回 k = 5，并且 nums 中的前五個元素為 0,0,1,3,4。
注意這五個元素可以任意順序返回。
你在返回的 k 個元素之外留下了什么并不重要（因此它們并不計入評測）。
提示：
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100
v1-基本
思路
首先要搞清楚要做什么：
1）移除所有和 val 相同的元素
2）返回和 val 不同的個數(shù)
其中返回元素的順序不重要
也就是我們可以用 swap 來交換位置實現(xiàn)。
不要 swap 的時候要注意，要一直找到第一個不等于 val 的 swap。
實現(xiàn)
class Solution {
public int removeElement(int[] nums, int val) {
int left = 0;
int right = nums.length-1;
while(left <= right) {
int num = nums[left];
if(num == val) {
// swap 找到不等于 val 的元素
while(nums[right] == val && left < right) {
right--;
}
// 提前結束
if(left >= right) {
return left;
}
swap(nums, left, right);
right--;
} else {
left++;
}
}
return left;
}
private void swap(int[] nums, int ix1, int ix2) {
int temp = nums[ix1];
nums[ix1] = nums[ix2];
nums[ix2] = temp;
}
}
效果
0ms 擊敗 100.00%
復雜度
時間復雜度：O(n)
空間復雜度：O(1)
反思
這種一般都是利用 swap 來實現(xiàn)。
v2-雙指針賦值
思路
這個系統(tǒng) LC26 我是后面做的，發(fā)現(xiàn)也可以用來解決這一題。
思路類似。
left 指向“刪除后數(shù)組的最后一個有效位置”
right 用來掃描整個數(shù)組
如果發(fā)現(xiàn)不等于 val，就把它放到 left+1 的位置上
實現(xiàn)
class Solution {
public int removeElement(int[] nums, int val) {
int left = 0;
for(int right = 0; right < nums.length; right++) {
if(nums[right] != val) {
nums[left++] = nums[right];
}
}
return left;
}
}
效果
0ms 100%
反思
還是比較喜歡這個版本。
可以保障有序性，同時比 v2 其實簡潔不少，不容易寫錯。
同時 LC26 和 LC27 的解法可以基本類似。
開源地址
為了便于大家學習，所有實現(xiàn)均已開源。歡迎 fork + star~
