소개
이 게시물에서는 상대 순서를 유지하면서 배열에서 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이 아닌 배열, 빈 배열, 초기화되지 않은 배열 등 다양한 시나리오를 보여주는 다양한 테스트 사례가 포함되어 있습니다.
고려되는 엣지 케이스
빈 배열: 프로그램은 예외를 발생시키지 않고 빈 배열을 처리합니다.
초기화되지 않은 어레이: 초기화되지 않은 어레이에 대한 테스트 사례의 주석 처리를 제거하면 컴파일 오류가 발생하여 어레이 초기화의 중요성을 보여줍니다.
결론
이 프로그램은 0이 아닌 값을 배열에서 오른쪽으로 이동하는 효율적인 방법을 제공합니다. 이는 시간과 공간의 복잡성 측면에서 세심한 포인터 관리가 어떻게 최적의 솔루션으로 이어질 수 있는지 보여주는 훌륭한 예입니다.
배열에 대한 또 다른 일반적인 인터뷰 질문은 0이 아닌 값을 왼쪽으로 이동: 일반적인 배열 인터뷰 문제-1에 대한 이전 게시물을 확인하세요.
질문이나 제안사항이 있으면 아래에 댓글을 남겨주세요. 즐거운 코딩하세요!
위 내용은 0이 아닌 값을 오른쪽으로 이동: 공통 배열 인터뷰 문제-2의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

핫 AI 도구

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

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

Undress AI Tool
무료로 이미지를 벗다

Clothoff.io
AI 옷 제거제

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

인기 기사

뜨거운 도구

MinGW - Windows용 미니멀리스트 GNU
이 프로젝트는 osdn.net/projects/mingw로 마이그레이션되는 중입니다. 계속해서 그곳에서 우리를 팔로우할 수 있습니다. MinGW: GCC(GNU Compiler Collection)의 기본 Windows 포트로, 기본 Windows 애플리케이션을 구축하기 위한 무료 배포 가능 가져오기 라이브러리 및 헤더 파일로 C99 기능을 지원하는 MSVC 런타임에 대한 확장이 포함되어 있습니다. 모든 MinGW 소프트웨어는 64비트 Windows 플랫폼에서 실행될 수 있습니다.

드림위버 CS6
시각적 웹 개발 도구

WebStorm Mac 버전
유용한 JavaScript 개발 도구

ZendStudio 13.5.1 맥
강력한 PHP 통합 개발 환경

메모장++7.3.1
사용하기 쉬운 무료 코드 편집기
