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

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이 아닌 요소를 올바른 위치로 이동하는 것입니다.

  1. 포인터 초기화: 배열의 마지막 인덱스에 포인터를 설정하는 것부터 시작하세요. 이 포인터는 0이 아닌 다음 값이 배치되어야 하는 위치를 표시합니다.
  2. 배열 탐색: 배열을 오른쪽에서 왼쪽으로 이동합니다. 0이 아닌 요소가 발견될 때마다 포인터가 가리키는 위치에 배치하고 포인터를 감소시킵니다.
  3. 나머지 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

    }
}

코드 설명

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

고려되는 엣지 케이스

  • 빈 배열: 프로그램은 예외를 발생시키지 않고 빈 배열을 처리합니다.

  • 초기화되지 않은 어레이: 초기화되지 않은 어레이에 대한 테스트 사례의 주석 처리를 제거하면 컴파일 오류가 발생하여 어레이 초기화의 중요성을 보여줍니다.

결론

이 프로그램은 0이 아닌 값을 배열에서 오른쪽으로 이동하는 효율적인 방법을 제공합니다. 이는 시간과 공간의 복잡성 측면에서 세심한 포인터 관리가 어떻게 최적의 솔루션으로 이어질 수 있는지 보여주는 훌륭한 예입니다.

배열에 대한 또 다른 일반적인 인터뷰 질문은 0이 아닌 값을 왼쪽으로 이동: 일반적인 배열 인터뷰 문제-1에 대한 이전 게시물을 확인하세요.

질문이나 제안사항이 있으면 아래에 댓글을 남겨주세요. 즐거운 코딩하세요!

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

성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
2025 년 상위 4 개의 JavaScript 프레임 워크 : React, Angular, Vue, Svelte2025 년 상위 4 개의 JavaScript 프레임 워크 : React, Angular, Vue, SvelteMar 07, 2025 pm 06:09 PM

이 기사는 2025 년에 상위 4 개의 JavaScript 프레임 워크 (React, Angular, Vue, Svelte)를 분석하여 성능, 확장 성 및 향후 전망을 비교합니다. 강력한 공동체와 생태계로 인해 모두 지배적이지만 상대적으로 대중적으로

카페인 또는 구아바 캐시와 같은 라이브러리를 사용하여 자바 애플리케이션에서 다단계 캐싱을 구현하려면 어떻게해야합니까?카페인 또는 구아바 캐시와 같은 라이브러리를 사용하여 자바 애플리케이션에서 다단계 캐싱을 구현하려면 어떻게해야합니까?Mar 17, 2025 pm 05:44 PM

이 기사는 카페인 및 구아바 캐시를 사용하여 자바에서 다단계 캐싱을 구현하여 응용 프로그램 성능을 향상시키는 것에 대해 설명합니다. 구성 및 퇴거 정책 관리 Best Pra와 함께 설정, 통합 및 성능 이점을 다룹니다.

Node.js 20 : 주요 성능 향상 및 새로운 기능Node.js 20 : 주요 성능 향상 및 새로운 기능Mar 07, 2025 pm 06:12 PM

Node.js 20은 V8 엔진 개선, 특히 더 빠른 쓰레기 수집 및 I/O를 통해 성능을 크게 향상시킵니다. 새로운 기능에는 더 나은 webAssembly 지원 및 정제 디버깅 도구, 개발자 생산성 및 응용 속도 향상이 포함됩니다.

Java의 클래스로드 메커니즘은 다른 클래스 로더 및 대표 모델을 포함하여 어떻게 작동합니까?Java의 클래스로드 메커니즘은 다른 클래스 로더 및 대표 모델을 포함하여 어떻게 작동합니까?Mar 17, 2025 pm 05:35 PM

Java의 클래스 로딩에는 부트 스트랩, 확장 및 응용 프로그램 클래스 로더가있는 계층 적 시스템을 사용하여 클래스로드, 링크 및 초기화 클래스가 포함됩니다. 학부모 위임 모델은 핵심 클래스가 먼저로드되어 사용자 정의 클래스 LOA에 영향을 미치도록합니다.

Spring Boot Snakeyaml 2.0 CVE-2022-1471 문제 고정Spring Boot Snakeyaml 2.0 CVE-2022-1471 문제 고정Mar 07, 2025 pm 05:52 PM

이 기사는 원격 코드 실행을 허용하는 중요한 결함 인 Snakeyaml의 CVE-2022-1471 취약점을 다룹니다. Snakeyaml 1.33 이상으로 Spring Boot 응용 프로그램을 업그레이드하는 방법에 대해 자세히 설명합니다.

빙산 : 데이터 호수 테이블의 미래빙산 : 데이터 호수 테이블의 미래Mar 07, 2025 pm 06:31 PM

대규모 분석 데이터 세트를위한 오픈 테이블 형식 인 Iceberg는 데이터 호수 성능 및 확장 성을 향상시킵니다. 내부 메타 데이터 관리를 통한 Parquet/Orc의 한계를 해결하여 효율적인 스키마 진화, 시간 여행, 동시 W를 가능하게합니다.

Java에서 기능 프로그래밍 기술을 어떻게 구현할 수 있습니까?Java에서 기능 프로그래밍 기술을 어떻게 구현할 수 있습니까?Mar 11, 2025 pm 05:51 PM

이 기사는 Lambda 표현식, 스트림 API, 메소드 참조 및 선택 사항을 사용하여 기능 프로그래밍을 Java에 통합합니다. 간결함과 불변성을 통한 개선 된 코드 가독성 및 유지 관리 가능성과 같은 이점을 강조합니다.

오이의 단계간에 데이터를 공유하는 방법오이의 단계간에 데이터를 공유하는 방법Mar 07, 2025 pm 05:55 PM

이 기사는 오이 단계간에 데이터를 공유하는 방법, 시나리오 컨텍스트, 글로벌 변수, 인수 통과 및 데이터 구조를 비교합니다. 간결한 컨텍스트 사용, 설명을 포함하여 유지 관리에 대한 모범 사례를 강조합니다.

See all articles

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

AI Hentai Generator

AI Hentai Generator

AI Hentai를 무료로 생성하십시오.

뜨거운 도구

맨티스BT

맨티스BT

Mantis는 제품 결함 추적을 돕기 위해 설계된 배포하기 쉬운 웹 기반 결함 추적 도구입니다. PHP, MySQL 및 웹 서버가 필요합니다. 데모 및 호스팅 서비스를 확인해 보세요.

DVWA

DVWA

DVWA(Damn Vulnerable Web App)는 매우 취약한 PHP/MySQL 웹 애플리케이션입니다. 주요 목표는 보안 전문가가 법적 환경에서 자신의 기술과 도구를 테스트하고, 웹 개발자가 웹 응용 프로그램 보안 프로세스를 더 잘 이해할 수 있도록 돕고, 교사/학생이 교실 환경 웹 응용 프로그램에서 가르치고 배울 수 있도록 돕는 것입니다. 보안. DVWA의 목표는 다양한 난이도의 간단하고 간단한 인터페이스를 통해 가장 일반적인 웹 취약점 중 일부를 연습하는 것입니다. 이 소프트웨어는

SublimeText3 영어 버전

SublimeText3 영어 버전

권장 사항: Win 버전, 코드 프롬프트 지원!

Eclipse용 SAP NetWeaver 서버 어댑터

Eclipse용 SAP NetWeaver 서버 어댑터

Eclipse를 SAP NetWeaver 애플리케이션 서버와 통합합니다.

Dreamweaver Mac版

Dreamweaver Mac版

시각적 웹 개발 도구