介绍
在这篇文章中，我们将探索如何将数组中的所有非零值向右移动，同时保持其相对顺序。这个问题是一个常见的面试问题，测试你对数组操作和算法优化的理解。让我们深入研究使用 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方法包含各种测试用例来演示不同的场景，例如以非零或零值结尾的数组、全零或全非零的数组、空数组和未初始化的数组。
考虑的边缘情况
空数组：程序处理空数组而不引发异常。
未初始化的数组：取消未初始化数组的测试用例的注释将导致编译错误，这说明了数组初始化的重要性。
结论
该程序提供了一种将数组中的非零值向右移动的有效方法。这是一个很好的例子，说明了仔细的指针管理如何能够在时间和空间复杂性方面带来最佳解决方案。
有关数组的另一个常见面试问题，请查看我之前的文章《向左移动非零值：常见数组面试问题-1》
如果您有任何疑问或建议，请随时在下面留言。快乐编码！
