左移非零值：公共數組面試問題 1

介紹

在技術面試中，常常會遇到陣列操作問題。在這篇文章中，我們將解決一個常見問題：將非零值向左移動，同時保持非零元素的順序並將所有零推到右側。

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

問題陳述

給定一個整數數組，您的任務是將所有非零元素移動到左側，同時將所有零元素推到右側。必須保留非零元素的相對順序。

範例：

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)。

1. 使用指標追蹤下一個非零元素的索引。
2. 迭代數組，將非零元素放置在指標的索引處。
3. 每次放置非零元素時都會增加指針。

守則

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
    }

}

解釋

• shiftValues 方法迭代輸入陣列。

• 如果找到非零值，則將其放置在目前指標索引處，並將目前索引處的元素替換為 0。

• 然後指標遞增以追蹤非零元素的下一個位置。

• 如果正確位置（即指標索引處）已經有一個非零值，則該方法只是遞增指標而不進行任何交換。

• 這將持續到處理整個陣列為止。

時間和空間複雜性

• 時間複雜度： O(n)，其中 n 是陣列的長度。

• 空間複雜度： O(1)，因為我們正在就地修改陣列。

邊緣情況

• 全零：如果陣列包含全零，則保持不變。

• 沒有零：如果沒有零，則保留元素的原始順序。

• 空數組： 函數應該毫無問題地處理空數組。

結論

這個問題展示了理解數組操作技術及其在編碼面試中的效率的重要性。掌握這樣的問題可以大大提升你解決問題的能力！

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