[LeetCode] 905. Sort Array By Parity - 문제풀이

Description

정수 배열이 주어졌을때 짝수를 모두 배열의 시작부분에 먼저 위치시키는 문제입니다.

Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers.

Return any array that satisfies this condition.

Example 1:

Input: nums = [3,1,2,4]
Output: [2,4,3,1]
Explanation: The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Example 2:

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

Constraints:

• 1 <= nums.length <= 5000
• 0 <= nums[i] <= 5000

Solution 1. Two Pointers

public int[] sortArrayByParity(int[] nums) {

    if(nums.length<2){return nums;} //edge case

    //1. inplace operation 퀵정렬
    int index = 0;

    for (int i = 0; i < nums.length ; i++) {
        if(nums[i]%2 == 0){
            //swap
            int temp = nums[index];
            nums[index++] = nums[i];
            nums[i] = temp;
        }
    }

    return nums;

}

짝수로 swap 할 위치의 index를 기억하고 있다가 짝수를 만나면 swap하고 인덱스를 하나 추가해줍니다.

• 시간복잡도 O(N)

Solution 2. Stream

public int[] sortArrayByParity(int[] nums) {

    if(nums.length<2){return nums;} //edge case

    // Stream
    return IntStream.concat(IntStream.of(nums).filter(a->a % 2==0).sorted(), IntStream.of(nums).filter(a->a % 2!=0).sorted()).toArray();

}

스트림을 통해 짝수, 홀수 array를 각각 필터링해서 만든 뒤 두 배열 스트림을 concat하여 반환하는 함수형프로그래밍 방법입니다. 시간복잡도는 O(N)이 두번 들어가 더 효율은 떨어집니다.

Reference

Sort Array By Parity - LeetCode