右移非零值：公共数组面试问题 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》。

如果您有任何问题或建议，请随时在下面留言。快乐编码！

以上是右移非零值：公共数组面试问题 详情请关注图灵教育的其他相关文章！