右移非零值:公共数组面试问题 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 >= 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》
如果您有任何疑问或建议,请随时在下面留言。快乐编码!
以上是右移非零值:公共数组面试问题 2的详细内容。更多信息请关注PHP中文网其他相关文章!

热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

Video Face Swap
使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热门文章

热工具

记事本++7.3.1
好用且免费的代码编辑器

SublimeText3汉化版
中文版,非常好用

禅工作室 13.0.1
功能强大的PHP集成开发环境

Dreamweaver CS6
视觉化网页开发工具

SublimeText3 Mac版
神级代码编辑软件(SublimeText3)

公司安全软件导致部分应用无法正常运行的排查与解决方法许多公司为了保障内部网络安全,会部署安全软件。...

系统对接中的字段映射处理在进行系统对接时,常常会遇到一个棘手的问题:如何将A系统的接口字段有效地映�...

在使用MyBatis-Plus或其他ORM框架进行数据库操作时,经常需要根据实体类的属性名构造查询条件。如果每次都手动...

将姓名转换为数字以实现排序的解决方案在许多应用场景中,用户可能需要在群组中进行排序,尤其是在一个用...

在使用IntelliJIDEAUltimate版本启动Spring...

Java对象与数组的转换:深入探讨强制类型转换的风险与正确方法很多Java初学者会遇到将一个对象转换成数组的�...

电商平台SKU和SPU表设计详解本文将探讨电商平台中SKU和SPU的数据库设计问题,特别是如何处理用户自定义销售属...

在使用TKMyBatis进行数据库查询时,如何优雅地获取实体类变量名以构建查询条件,是一个常见的难题。本文将针...
