0이 아닌 값을 왼쪽으로 이동: 일반적인 배열 인터뷰 문제-1

소개

기술 면접에서는 배열 조작 문제가 자주 발생합니다. 이번 게시물에서는 0이 아닌 요소의 순서를 유지하고 모든 0을 오른쪽으로 푸시하면서 0이 아닌 값을 왼쪽으로 이동하는 일반적인 문제를 다루겠습니다.

기본 배열 개념에 익숙하지 않다면 Java의 배열 기본 이해: 속도를 높이기 위한 간단한 가이드를 확인하는 것이 좋습니다!

문제 설명

정수 배열이 주어지면 0이 아닌 모든 요소를 ​​왼쪽으로 이동하고 모든 0 요소를 오른쪽으로 밀어내는 것이 임무입니다. 0이 아닌 요소의 상대적 순서는 유지되어야 합니다.

예:

Input:  [1, 2, 0, 3, 0, 0, 4, 3, 2, 9]
Output: [1, 2, 3, 4, 3, 2, 9, 0, 0, 0]

접근하다

배열을 통한 단일 패스를 사용하여 O(n) 시간 내에 이 문제를 해결할 수 있으며, 솔루션의 공간 복잡도는 O(1)입니다.

1. 포인터를 사용하여 0이 아닌 다음 요소의 색인을 추적하세요.
2. 배열을 반복하여 포인터의 인덱스에 0이 아닌 요소를 배치합니다.
3. 0이 아닌 요소가 배치될 때마다 포인터를 증가시킵니다.

코드

package arrays;

// Time Complexity - O(n)
// Space Complexity - O(1)
public class ShiftNonZeroValuesToLeft {

    private void shiftValues(int[] inputArray) {

        /* Variable to keep track of index position to be 
                   filled with Non-Zero Value */ 
        int pointer = 0;

        // If value is Non-Zero then place it at the pointer index
        for (int i = 0; i < inputArray.length; i++) {

            /* If there is a non-zero already at correct position, 
                     just increment position */
            if (inputArray[i] != 0) {

                if (i != pointer) {
                    inputArray[pointer] = inputArray[i];
                    inputArray[i] = 0;
                }

                pointer++;
            }
        }

        // Printing result using for-each loop
        for (int i : inputArray) {
            System.out.print(i);
        }

        System.out.println();
    }

    public static void main(String[] args) {

        // Test-Case-1 : Starting with a Non-Zero
        int input1[] = { 1, 2, 0, 3, 0, 0, 4, 3, 2, 9 };

        // Test-Case-2 : Starting with Zero
        int input2[] = { 0, 5, 1, 0, 2, 0, 9 };

        // Test-Case-3 : All Zeros
        int input3[] = { 0, 0, 0, 0 };

        // Test-Case-4 : All Non-Zeros
        int input4[] = { 1, 2, 3, 4 };

        // Test-Case-5 : Empty Array
        int input5[] = {};

        // Test-Case-6 : Empty Array
        int input6[] = new int[5];

        // Test-Case-7 : Uninitialized Array
        int input7[];

        ShiftNonZeroValuesToLeft classObject = new ShiftNonZeroValuesToLeft();
        classObject.shiftValues(input1); // Result : 1234329000
        classObject.shiftValues(input2); // Result : 5129000
        classObject.shiftValues(input3); // Result : 0000
        classObject.shiftValues(input4); // Result : 1234
        classObject.shiftValues(input5); // Result : 
        classObject.shiftValues(input6); // Result : 00000
        classObject.shiftValues(input7); // Result : Compilation Error - Array may not have been initialized
    }

}

설명

• shiftValues 메소드는 입력 배열을 반복합니다.

• 0이 아닌 값이 발견되면 현재 포인터 인덱스에 배치되고 현재 인덱스의 요소는 0으로 대체됩니다.

• 그런 다음 0이 아닌 요소의 다음 위치를 추적하기 위해 포인터가 증가합니다.

• 올바른 위치(즉, 포인터 인덱스)에 이미 0이 아닌 값이 있는 경우 메서드는 교체를 하지 않고 단순히 포인터를 증가시킵니다.

• 이 작업은 전체 배열이 처리될 때까지 계속됩니다.

시간과 공간의 복잡성

• 시간 복잡도: O(n), 여기서 n은 배열의 길이입니다.

• 공간 복잡도: O(1), 어레이를 제자리에서 수정하고 있기 때문입니다.

엣지 케이스

• 모두 0: 배열에 모두 0이 포함되어 있으면 변경되지 않습니다.

• 0 없음: 0이 없으면 요소의 원래 순서가 유지됩니다.

• 빈 배열: 함수는 문제 없이 빈 배열을 처리해야 합니다.

결론

이 문제는 코딩 인터뷰에서 배열 조작 기술과 그 효율성을 이해하는 것이 얼마나 중요한지 보여줍니다. 이러한 문제를 마스터하면 문제 해결 능력이 크게 향상될 수 있습니다!

위 내용은 0이 아닌 값을 왼쪽으로 이동: 일반적인 배열 인터뷰 문제-1의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!