首页 Java java教程 右移非零值:公共数组面试问题 2

右移非零值:公共数组面试问题 2

Sep 25, 2024 am 06:23 AM

Shifting Non-Zero Values Right : A Common Array Interview Problem-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》

如果您有任何疑问或建议,请随时在下面留言。快乐编码!

以上是右移非零值:公共数组面试问题 2的详细内容。更多信息请关注PHP中文网其他相关文章!

本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

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

AI Clothes Remover

AI Clothes Remover

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

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

Video Face Swap

Video Face Swap

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

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

公司安全软件导致应用无法运行?如何排查和解决? 公司安全软件导致应用无法运行?如何排查和解决? Apr 19, 2025 pm 04:51 PM

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

如何使用MapStruct简化系统对接中的字段映射问题? 如何使用MapStruct简化系统对接中的字段映射问题? Apr 19, 2025 pm 06:21 PM

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

如何优雅地获取实体类变量名构建数据库查询条件? 如何优雅地获取实体类变量名构建数据库查询条件? Apr 19, 2025 pm 11:42 PM

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

如何将姓名转换为数字以实现排序并保持群组中的一致性? 如何将姓名转换为数字以实现排序并保持群组中的一致性? Apr 19, 2025 pm 11:30 PM

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

IntelliJ IDEA是如何在不输出日志的情况下识别Spring Boot项目的端口号的? IntelliJ IDEA是如何在不输出日志的情况下识别Spring Boot项目的端口号的? Apr 19, 2025 pm 11:45 PM

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

Java对象如何安全地转换为数组? Java对象如何安全地转换为数组? Apr 19, 2025 pm 11:33 PM

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

电商平台SKU和SPU数据库设计:如何兼顾用户自定义属性和无属性商品? 电商平台SKU和SPU数据库设计:如何兼顾用户自定义属性和无属性商品? Apr 19, 2025 pm 11:27 PM

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

使用TKMyBatis进行数据库查询时,如何优雅地获取实体类变量名构建查询条件? 使用TKMyBatis进行数据库查询时,如何优雅地获取实体类变量名构建查询条件? Apr 19, 2025 pm 09:51 PM

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

See all articles