Leetcode 27:要素の除去(最も詳細な解決策!!)

配列numsと値valを指定すると、valに等しいすべての数値の要素をその場で除去し、除去後の配列の新しい長さを返す必要があります.
余分な配列空間を使用しないでください.入力配列をその場で変更し、O(1)余分な空間を使用する条件で完了する必要があります.
要素の順序は変更できます.配列の中で新しい長さの後ろを超える要素を考慮する必要はありません.
例1:

   nums = [3,2,2,3], val = 3,
           2,    nums           2。
                   。

例2:

   nums = [0,1,2,2,3,0,4,2], val = 2,
           5,    nums          0, 1, 3, 0, 4。
             。
                   。

説明:
なぜ返される数値は整数ですが、出力される答えは配列ですか?
入力配列は**の「参照」**で渡されます.これは、関数で入力配列を変更することが呼び出し元に表示されることを意味します.
内部操作は次のように想像できます.

// nums   “  ”     。    ，         
int len = removeElement(nums, val);
//                    。
//            ,                    。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

問題を解く構想.
この問題の解決策Leetcode 283:移動ゼロ(最も詳細な解決策)を参照して、類似の解決策をすぐに書きます.

class Solution:
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        k = 0
        for i, num in enumerate(nums):
            if num != val:
                if i != k:
                    nums[i], nums[k] = nums[k], nums[i]
                k += 1
        return k

しかし,この問題については,元素を交換すると同時にvalでない場合を考慮したため,この解法が最適ではないことが明らかになった.実際には私たちは彼らを全く考えなくてもいいです.

class Solution:
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        k = 0
        for i, num in enumerate(nums):
            if num != val:
                if i != k:
                    nums[k] = num #    
                k += 1
        return k

実際、ここの考えはモア投票アルゴリズムを参考にしたものだ.もちろん、選択可能な別のポリシーは、del要素によって結果を取得することである.

class Solution:
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        val_num = nums.count(val)
        for _ in range(val_num):
            nums.remove(val)

ここに罠があることに注意してください.私たちは次のような方法ではいけません.

class Solution:
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        k = len(nums)
        for i, num in enumerate(nums):
            if num == val:
                del nums[i]
                k -= 1

        return k

ループ内でdel操作を用いたため,nums前後に変化が生じ,このときのインデックスも変化する.こうすべきだ

class Solution:
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :rtype: int
        """
        k = 0
        nums_len = len(nums)
        while k < nums_len:
            if nums[k] == val:
                del nums[k]
                nums_len -= 1
            else:
                k += 1
        return nums_len

この問題の他の言語バージョンは私のGitHub Leetcodeに追加されました.
もし問題があれば、皆さんに指摘してほしい!!!