0이 아닌 값을 오른쪽으로 이동: 공통 배열 인터뷰 문제-2-java지도 시간-php.cn

0이 아닌 값을 오른쪽으로 이동: 공통 배열 인터뷰 문제-2

Patricia Arquette

풀어 주다： 2024-09-25 06:23:07

원래의

504명이 탐색했습니다.

Shifting Non-Zero Values Right : A Common Array Interview Problem-2

소개

이 게시물에서는 상대 순서를 유지하면서 배열에서 0이 아닌 모든 값을 오른쪽으로 이동하는 방법을 살펴보겠습니다. 이 문제는 배열 조작 및 알고리즘 최적화에 대한 이해를 테스트하는 일반적인 인터뷰 질문입니다. Java를 활용한 솔루션을 살펴보겠습니다.

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

문제 설명

정수 배열이 주어지면 순서를 유지하면서 0이 아닌 모든 값을 오른쪽으로 이동하려고 합니다. 0 값은 왼쪽으로 이동해야 합니다.

예:

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

로그인 후 복사

접근하다

이 문제를 해결하기 위해 색인 추적 접근 방식을 사용하겠습니다. 목표는 배열을 오른쪽에서 왼쪽으로 반복하고 0이 아닌 요소를 올바른 위치로 이동하는 것입니다.

포인터 초기화: 배열의 마지막 인덱스에 포인터를 설정하는 것부터 시작하세요. 이 포인터는 0이 아닌 다음 값이 배치되어야 하는 위치를 표시합니다.
배열 탐색: 배열을 오른쪽에서 왼쪽으로 이동합니다. 0이 아닌 요소가 발견될 때마다 포인터가 가리키는 위치에 배치하고 포인터를 감소시킵니다.
나머지 0: 0이 아닌 요소를 모두 재배치한 후 배열 시작 부분(즉, 포인터 왼쪽)의 사용되지 않은 지점에는 자동으로 0이 포함됩니다.

이 접근 방식은 O(n)의 시간 복잡도와 O(1)의 공간 복잡도를 가지므로 효율적이면서도 공간을 절약할 수 있습니다.

구현

package arrays;

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

    private void shiftValues(int[] inputArray) {

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

        // If value is Non-Zero then place it at the pointer index
        for (int i = pointer; i >= 0; i--) {

            /* If there is a non-zero already at correct position,
               just decrement 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 : Ending with a Non-Zero
        int input1[] = { 1, 2, 0, 3, 0, 0, 4, 0, 2, 9 };

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

        // 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[];

        ShiftNonZeroValuesToRight classObject = new ShiftNonZeroValuesToRight();
        classObject.shiftValues(input1); // Result : 0000123429
        classObject.shiftValues(input2); // Result : 0008515
        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 메서드:
- 입력 매개변수: inputArray – 처리해야 하는 배열입니다.
- 포인터 초기화: 포인터가 배열의 마지막 인덱스로 초기화됩니다.
- 배열 순회: 루프는 배열 끝에서 시작 부분을 향해 반복되며 0이 아닌 요소를 확인합니다. 0이 아닌 요소는 포인터가 가리키는 위치로 이동하고 포인터는 감소됩니다.
- 결과: 0이 아닌 모든 요소가 이동되면 배열의 나머지 요소는 추가 단계 없이 자연스럽게 0이 됩니다.
주요 방법:
- 기본 메소드에는 0이 아니거나 0이 아닌 값으로 끝나는 배열, 모두 0이거나 모두 0이 아닌 배열, 빈 배열, 초기화되지 않은 배열 등 다양한 시나리오를 보여주는 다양한 테스트 사례가 포함되어 있습니다.