[LeetCode] 283. Move Zeroes

Problem

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 <= 10^4
• -2^31 <= nums[i] <= 2^31 - 1

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

Solution

Logic

1. 배열에서 0이 아닌 요소를 참조하게 되면 배열 중 정렬되지 않은 제일 앞 자리에 할당하며 배열의 모든 요소를 참조한다.

2. 배열 중 정렬되지 않고 남은 부분의 요소들에 전부 0을 할당한다.

   Code

   class Solution {
    public void moveZeroes(int[] nums) {
        int cnt = 0;
        for (int i = 0; i < nums.length; i++)
            if (nums[i] != 0) nums[cnt++] = nums[i];
        for (int i = cnt; i < nums.length; i++)
            nums[i] = 0;
    }
   }
   

   Time Complexity

   • 배열 nums의 길이를 n이라 가정할 때, 코드의 수행 시간을 좌우하는 것은 첫 번째 for반복문의 n번 계산 횟수이다. 따라서 본 솔루션은 O(n)의 시간 복잡도를 가진다.