右移非零值：公共數組面試問題 2-java教程-PHP中文網

右移非零值：公共數組面試問題 2

Patricia Arquette

發布： 2024-09-25 06:23:07

原創

504 人瀏覽過

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

介紹

在這篇文章中，我們將探索如何將陣列中的所有非零值向右移動，同時保持其相對順序。這個問題是一個常見的面試問題，測試你對陣列操作和演算法最佳化的理解。讓我們深入研究使用 Java 的解決方案。

如果您不熟悉基本的陣列概念，我建議您查看《Understanding Array Basics in Java: A Simple Guide》以快速入門！

問題陳述

給定一個整數數組，我們希望將所有非零值向右移動，同時保留它們的順序。零值應移至左側。

範例：

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

登入後複製

方法

我們將使用索引追蹤方法來解決這個問題。目標是從右到左迭代數組並將非零元素移動到正確的位置。

初始化指標： 首先在陣列的最後一個索引處設定一個指標。此指標將標記下一個非零值應放置的位置。
遍歷陣列：從右向左遍歷陣列。對於遇到的每個非零元素，將其放置在指標指示的位置，並遞減指標。
剩餘的零：重新定位所有非零元素後，數組開頭（即指針左側）的任何未使用的點將自動包含零。

此方法的時間複雜度為 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 – 需要處理的陣列。
- 指標初始化：指標初始化為陣列的最後一個索引。
- 陣列遍歷： 迴圈從陣列結尾向開頭迭代，檢查非零元素。非零元素移動到指標指示的位置，並且指標遞減。
- 結果：一旦移動了所有非零元素，數組中剩餘的元素自然會為零，無需任何額外步驟。
主要方法：
- main方法包含各種測試案例來示範不同的場景，例如以非零或零值結尾的陣列、全零或全非零的陣列、空數組和未初始化的陣列。