0이 아닌 값을 왼쪽으로 이동: 일반적인 배열 인터뷰 문제-1-java지도 시간-php.cn

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

Linda Hamilton

풀어 주다： 2024-09-23 22:15:39

원래의

790명이 탐색했습니다.

Shifting Non-Zero Values Left: A Common Array Interview Problem-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)입니다.

포인터를 사용하여 0이 아닌 다음 요소의 색인을 추적하세요.
배열을 반복하여 포인터의 인덱스에 0이 아닌 요소를 배치합니다.
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
    }

}

로그인 후 복사