【LittleDuck_LeetCodeNote】27 - Remove Element

更新於 發佈於 閱讀時間約 9 分鐘

【Instagram】 / 【巴哈姆特小屋】 / 【Vocus方格子】 / 【Medium】
喜歡的話就按個愛心或贊助ㄅ。


raw-image

Question and Hints:

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

  • Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
  • Return k.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
// It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

Example 1:

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100

First Solution

💡 這題的思路是參考Quick Sort的作法:兩個索引 i 和 j,
i 從前面往後數尋找應該刪除的值,
j 從後面往前數尋找未被刪除的值,
將所有與val相同的值丟到陣列後面,
最後從頭檢查,直到發現val為止,
如此就能得到新的陣列與長度。
class Solution {
public int removeElement(int[] nums, int val) {
// except: nums.len<2
if(nums.length == 0 || nums.length == 1 && nums[0] == val)
return 0;

int i=0, j=nums.length-1;
int temp;

while(i < j){
if(nums[i] == val){
while(i < j && nums[j] == val){
j--;
if(i >= j)
return i;
if(j <= -1)
return 0;
}
temp = nums[j];
nums[j] = nums[i];
nums[i] = temp;
j--;
}
i++;
}

int k = 1;
for(; k<nums.length; k++){
if(nums[k] == val)
break;
}

return k;
}
}

⏰ Runtime: 0 ms (100 %)

📦 Memory: 40.7 MB (97.78 %)



Upgrade Solution

💡 思路是相似的,只是它在index的用途不同:
兩個index都是由前往後數,
i 負責尋找未被刪除的值,
j 負責尋找應該刪除的值,
然後不做交換,而是直接取代裡面的值。

可以換個角度想像兩個索引的工作:
i 往前尋找新陣列的值,
j 鎖定在新陣列的最尾端,
一旦 i 找到值,就從陣列最尾端塞進去。
class Solution {
public int removeElement(int[] nums, int val) {
int j=0;
for(int i=0;i<nums.length;i++){
if(nums[i]!=val){
nums[j++]=nums[i];
}
}
return j;
}
}

⏰ Runtime: 0 ms (100 %)

📦 Memory: 40.2 MB (100 %)

留言
avatar-img
留言分享你的想法!
avatar-img
Steven SHIH的沙龍
6會員
36內容數
以英文和日文歌的翻譯為主,並從「歌曲裡的故事」這個角度去翻譯。畢竟自己只有中文算好而已 :D
Steven SHIH的沙龍的其他內容
2023/07/10
Find the Index of the First Occurrence in a String : 找出haystack在字串中第一次出現的index.
Thumbnail
2023/07/10
Find the Index of the First Occurrence in a String : 找出haystack在字串中第一次出現的index.
Thumbnail
2023/07/10
Remove Duplicates from Sorted Array : 將陣列中的重複值移除,並回傳陣列裡的元素總數。
Thumbnail
2023/07/10
Remove Duplicates from Sorted Array : 將陣列中的重複值移除,並回傳陣列裡的元素總數。
Thumbnail
2023/07/09
Merge Two Sorted Lists : 將兩個LinkedList合併成一個新的陣列,並將內容由小到大排序。
Thumbnail
2023/07/09
Merge Two Sorted Lists : 將兩個LinkedList合併成一個新的陣列,並將內容由小到大排序。
Thumbnail
看更多
你可能也想看
Thumbnail
題目敘述 題目會給我們一個輸入整數陣列arr,和一個初始化的刪除次數k? 我們可以任意選擇從arr中刪除k個陣列元素,請問最後留下來的數字,最少會有幾個不同的數字? 註: 最後不同的數字越少越好。 題目的原文敘述 測試範例 Example 1: Input: arr = [5,5
Thumbnail
題目敘述 題目會給我們一個輸入整數陣列arr,和一個初始化的刪除次數k? 我們可以任意選擇從arr中刪除k個陣列元素,請問最後留下來的數字,最少會有幾個不同的數字? 註: 最後不同的數字越少越好。 題目的原文敘述 測試範例 Example 1: Input: arr = [5,5
Thumbnail
題目 : 27. Remove Element
Thumbnail
題目 : 27. Remove Element
Thumbnail
雖然表面是一道移除元素的題目,但實際上考的還是搬移。 題目要求的是把val目標值移除,等價於 把非目標值的搬到前面,並且回傳這些剩下來的元素個數(也就是 陣列裡面,非目標值的元素總數​)。 請看下方範例,會更好理解。
Thumbnail
雖然表面是一道移除元素的題目,但實際上考的還是搬移。 題目要求的是把val目標值移除,等價於 把非目標值的搬到前面,並且回傳這些剩下來的元素個數(也就是 陣列裡面,非目標值的元素總數​)。 請看下方範例,會更好理解。
Thumbnail
這題就是經典的考排序驗算法, 不管在教科書、上機考、面試白板題都是一個很基本又滿熱門的題目。 題目會給定一個輸入陣列,要求我們實作一個排序演算法,把陣列元素從小到大排好。
Thumbnail
這題就是經典的考排序驗算法, 不管在教科書、上機考、面試白板題都是一個很基本又滿熱門的題目。 題目會給定一個輸入陣列,要求我們實作一個排序演算法,把陣列元素從小到大排好。
Thumbnail
Remove Element : 在陣列中刪除val後,回傳剩餘的元素個數。
Thumbnail
Remove Element : 在陣列中刪除val後,回傳剩餘的元素個數。
Thumbnail
Remove Duplicates from Sorted Array : 將陣列中的重複值移除,並回傳陣列裡的元素總數。
Thumbnail
Remove Duplicates from Sorted Array : 將陣列中的重複值移除,並回傳陣列裡的元素總數。
Thumbnail
Valid Parentheses : 確認input的括號是否符合成雙成對的規則,符合回傳true,否則回傳false.
Thumbnail
Valid Parentheses : 確認input的括號是否符合成雙成對的規則,符合回傳true,否則回傳false.
Thumbnail
Two Sum : 在Array中找出相加後與Target相同的兩個數字,並將他們的index存在新的陣列。
Thumbnail
Two Sum : 在Array中找出相加後與Target相同的兩個數字,並將他們的index存在新的陣列。
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News