Description

Move Zeroes - LeetCode

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?

Solution

• 처음엔 일단 배열을 하나 더 만들어서 풀었다.
  • 새 배열의 앞부터 채울 포인터 하나(non-zero), 뒤부터 채울 포인터 하나(zero)를 두고 0이 나오면 뒤 포인터를 이용해 채우고 0이 아닌 수가 나오면 앞 포인터를 이용한다.

// using additional array
    public void moveZeros(int[] nums) {
        int[] temp = new int[nums.length];
        int p1 = 0, p2 = nums.length - 1;
        for (int i : nums) {
            if (i == 0) {
                temp[p2] = i;
                p2--;
            } else {
                temp[p1] = i;
                p1++;
            }
        }

        for (int i = 0; i < nums.length; i++) {
            nums[i] = temp[i];
        }
    }

• 새로운 배열을 쓰지 않고 푸는 방법을 생각해봤는데 포인터를 두개 둬서 하나(p1)는 전체를 iterate하게 하고 다른 하나(p2)는 0만 트랙해서 p1이 0이 아닐 때 p1과 p2를 스왑해주는 방법을 생각해냈다. 근데 구현이 잘 안돼서 헤매다가 결국 디스커션 보드 보고 해결

// using two pointer
    public void moveZeros2(int[] nums) {
        int p = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                swap(nums, i, p);
                p++;
            }
        }
    }

    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

• 디스커션 보드에 좀 특이한 풀이도 있었다. 전체 배열을 돌면서 0이 아닌 수를 앞으로 땡기고 남은 수들은 0으로 채운다.

// move all non-zeros to front then fill the rest with zeros
    public void moveZeroes3(int[] nums) {
        int p = 0;
        for (int i : nums) {
            if (i != 0) {
                nums[p] = i;
                p++;
            }
        }

        for (int i = p; i < nums.length; i++) {
            nums[i] = 0;
        }
    }