283. Move Zeroes (使用 C 語言解題)

283. Move Zeroes

Solved

Easy

Topics

Companies

Hint

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]

Example 2:

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

 

Constraints:

• 1 <= nums.length <= 104
• -231 <= nums[i] <= 231 - 1

 

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

goole 翻譯：

給定一個整數數組 nums，將所有 0 移至其末尾，同時保持非零元素的相對順序。

想法一：

依序讀取陣列，把有值的依序寫回陣列中，其他的都設成0

寫法一：

void moveZeroes(int* nums, int numsSize) {
    int read = 0, write =  0;
    // 使用讀取 index(read)
    while(read < numsSize) {
        if(nums[read]) {
            // 把值寫回陣列中 (使用寫入 index(write))
            nums[write++] = nums[read];
        }
        read++;
    }
    // 剩下的全設定成 0
    for(; write<numsSize; write++)
        nums[write] = 0;
}

結果一：

結果還好，看看大神們如何優化的...

想法二：

改用互換值的方式

寫法二：

void moveZeroes(int* nums, int numsSize) {
    int write = 0, tmp ;
    for(int i=0; i < numsSize; i++) {
        if(*(nums+i)) {
            // 用交換的方式，把值寫回陣列中
            tmp = *(nums+i);
            *(nums+i) = *(nums+write);
            *(nums+write) = tmp;
            write++;
        }
    }
}

結果二：

結果還算不錯哦

後記：

在這裡，使用 *(nums+i) 的方式，比 nums[i] 還快
用 for 好像也比 while 快一些...