右移非零值：公共数组面试问题 2（数组.面试.右移非零值...）

wufei1232024-09-30java23

右移非零值：公共数组面试问题 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 &gt;= 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方法包含各种测试用例来演示不同的场景，例如以非零或零值结尾的数组、全零或全非零的数组、空数组和未初始化的数组。

考虑的边缘情况