iT邦幫忙

2021 iThome 鐵人賽

DAY 15
1
自我挑戰組

試煉之地 Leetcode 的挑戰系列 第 15

Leetcode 挑戰 Day 15 [27. Remove Element]

27. Remove Element


今天我們一起挑戰leetcode第27題Remove Element!

題目


Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.

Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

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).

今天題目看似很長,但其實要我們做的事情也很簡單,就是要我們把題目指定的數字val,從題目給我們的整數陣列中移除,並把剩下來的整數移到陣列頭的位置,我們並不用回傳陣列,只要回傳剩下來的整數總數目。此外,題目希望我們最多利用額外的big O(1)空間複雜度就完成這一題。

ForLoop


這題其實可以用簡單的for迴圈就能夠完成,只要我們走訪一次題目給我們的陣列,遇到不屬於題目指定要刪除的元素,我們就把他往前面放,並且建立一變數count,把他加一,這樣我們下次就能知道要放在下一個位置。而且在走訪完全部迴圈後,我們也可以簡單知道count就是我們要回傳的答案。

以下是python的程式碼

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        count = 0
        for i in range(len(nums)):
            if nums[i] != val:
                nums[count] = nums[i]
                count += 1
        return count

上一篇
Leetcode 挑戰 Day 14 [169. Majority Element]
下一篇
Leetcode 挑戰 Day 16 [231. Power of Two]
系列文
試煉之地 Leetcode 的挑戰19

尚未有邦友留言

立即登入留言