【LeetCode】283. Move Zeroes 解答・解説【Python】

問題
1. 原文
2. 内容
解答
1. 解答1：two pointer
2. 解答2：Rust
補足・参考・感想

問題

原文

Given an integer array nums, move all 0‘s to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example 1:

Input: nums = [0,1,0,3,12] Output: [1,3,12,0,0]

1
2

Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Example 2:

Input: nums = [0] Output: [0]

1
2

Input: nums = [0]
Output: [0]

Constraints:

1 <= nums.length <= 10⁴

-2³¹ <= nums[i] <= 2³¹ - 1

Follow up: Could you minimize the total number of operations done?

内容

整数配列numsが与えられるので、0以外の要素の相対的な順序を維持したまま、全ての0を配列の最後尾まで移動させてください。

※正しくない可能性があります。

解答

解答1：two pointer

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        #スローポインタ
        slow = 0
        
        for fast in range(len(nums)):
            #早いポインタが0以外、遅いポインタが0の時
            if nums[fast] != 0 and nums[slow] == 0:
                #お互いの要素の位置を入れ替える
                nums[slow], nums[fast] = nums[fast], nums[slow]
            #遅いポインタが0以外の時
            if nums[slow] != 0:
                #遅いポインタを進める
                slow += 1

class Solution:

def moveZeroes(self, nums: List[int]) -> None:

"""

Do not return anything, modify nums in-place instead.

"""

#スローポインタ

slow = 0

for fast in range(len(nums)):

#早いポインタが0以外、遅いポインタが0の時

if nums[fast] != 0 and nums[slow] == 0:

#お互いの要素の位置を入れ替える

nums[slow], nums[fast] = nums[fast], nums[slow]

#遅いポインタが0以外の時

if nums[slow] != 0:

#遅いポインタを進める

slow += 1

・2つのポインタ(リストのインデックス)を使う。

・slowを0で設定。特定の条件の時のみ進めるので遅い方のポインタになる。

・配列を左端から順に一巡して操作する。その際のループ変数はfast(早い方のポインタ)として、ループの度に1つ進む。

・fast番目の要素が0以外、slow番目の要素が0のときはお互いの位置を入れ替える

・slow番目の要素が0以外のときはslowを一つ進める。

・配列を左端から順に走査していくので、配列内の0以外の要素も左端から順に0と位置が入れ替えられる。0以外の要素の相対的な位置は変わらない。

解答2：Rust

impl Solution {
    pub fn move_zeroes(nums: &mut Vec<i32>) {
        let mut z = Vec::new();
        nums.retain(|x| {
            if *x != 0 { true } else {z.push(0); false}
        });
        &nums.append(&mut z);
    }
}

impl Solution {

pub fn move_zeroes(nums: &mut Vec<i32>) {

let mut z = Vec::new();

nums.retain(|x| {

if *x != 0 { true } else {z.push(0); false}

});

&nums.append(&mut z);

}

写経

補足・参考・感想

■補足

■参考

■感想

前：977. Squares of a Sorted Array

次：167. Two Sum II – Input Array Is Sorted

LeetCode 解答・解説記事一覧