右移非零值：公共數組面試問題 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]

方法

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

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

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

考慮的邊緣情況

• 空數組：程式處理空數組而不引發異常。

• 未初始化的數組：取消未初始化數組的測試案例的註釋將導致編譯錯誤，這說明了數組初始化的重要性。

結論

該程式提供了一種將陣列中的非零值向右移動的有效方法。這是一個很好的例子，說明了仔細的指針管理如何在時間和空間複雜性方面帶來最佳解決方案。

有關數組的另一個常見面試問題，請查看我之前的文章《向左移動非零值：常見數組面試問題-1》

如果您有任何疑問或建議，請隨時在下面留言。快樂編碼！

以上是右移非零值：公共數組面試問題 2的詳細內容。更多資訊請關注PHP中文網其他相關文章！