”工欲善其事,必先利其器。“—孔子《论语.录灵公》
首页 > 编程 > Java程序从给定堆栈中删除重复项

Java程序从给定堆栈中删除重复项

发布于2024-09-02
浏览:537

在本文中,我们将探讨两种在 Java 中从堆栈中删除重复元素的方法。我们将比较使用嵌套循环的简单方法和使用 HashSet 的更有效方法。目标是演示如何优化重复删除并评估每种方法的性能。

问题陈述

编写一个Java程序,从堆栈中删除重复元素。

输入

Stack data = initData(10L);

输出

Unique elements using Naive Approach: [1, 4, 3, 2, 8, 7, 5]
Time spent for Naive Approach: 18200 nanoseconds

Unique elements using Optimized Approach: [1, 4, 3, 2, 8, 7, 5]
Time spent for Optimized Approach: 34800 nanoseconds

要从给定堆栈中删除重复项,我们有两种方法 -

  • 天真的方法:创建两个嵌套循环来查看哪些元素已经存在并防止将它们添加到结果堆栈返回中。
  • HashSet方法:使用Set来存储唯一元素,并利用其O(1)复杂度来检查元素是否存在。

生成和克隆随机堆栈

下面是 Java 程序首先构建一个随机堆栈,然后创建它的副本以供进一步使用 -

private static Stack initData(Long size) {
    Stack stack = new Stack  ();
    Random random = new Random();
    int bound = (int) Math.ceil(size * 0.75);
    for (int i = 0; i  manualCloneStack(Stack  stack) {
    Stack  newStack = new Stack  ();
    for (Integer item: stack) {
        newStack.push(item);
    }
    return newStack;
}

initData 帮助创建一个具有指定大小和范围从 1 到 100 的随机元素的 Stack。

manualCloneStack 通过从另一个堆栈复制数据来帮助生成数据,用它来比较两种想法的性能。

使用 Naïve 方法从给定堆栈中删除重复项

以下是使用 Naïve 方法从给定堆栈中删除重复项的步骤 -

  • 启动计时器。
  • 创建一个空堆栈来存储唯一元素。
  • 使用while循环迭代并继续,直到原始堆栈为空弹出顶部元素。
  • 使用 resultStack.contains(element) 检查重复项以查看该元素是否已在结果堆栈中。
  • 如果该元素不在结果栈中,则将其添加到结果栈中。
  • 记录结束时间并计算总花费时间。
  • 返回结果

例子

下面是使用 Naïve 方法从给定堆栈中删除重复项的 Java 程序 -

public static Stack idea1(Stack stack) {
  long start = System.nanoTime();
  Stack resultStack = new Stack  ();

  while (!stack.isEmpty()) {
    int element = stack.pop();
    if (!resultStack.contains(element)) {
      resultStack.add(element);
    }
  }
  System.out.println("Time spent for idea1 is %d nanosecond".formatted(System.nanoTime() - start));
  return resultStack;
}

对于朴素方法,我们使用

while (!stack.isEmpty())
处理第一个循环遍历堆栈中的所有元素,第二个循环是
resultStack.contains(element)
检查元素是否已存在。

使用优化方法 (HashSet) 从给定堆栈中删除重复项

以下是使用优化方法从给定堆栈中删除重复项的步骤 -

  • 启动计时器
  • 创建一个 Set 来跟踪看到的元素(用于 O(1) 复杂性检查)。
  • 创建临时堆栈来存储唯一元素。
  • 使用 while循环进行迭代,直到堆栈为空。
  • 从堆栈中移除顶部元素。
  • 要检查重复项,我们将使用 seen.contains(element) 来检查该元素是否已在集合中。
  • 如果该元素不在集合中,则将其添加到可见堆栈和临时堆栈中。
  • 记录结束时间并计算总花费时间。
  • 返回结果

例子

下面是使用 HashSet 从给定堆栈中删除重复项的 Java 程序 -

public static Stack idea2(Stack stack) {
    long start = System.nanoTime();
    Set seen = new HashSet();
    Stack tempStack = new Stack();

    while (!stack.isEmpty()) {
        int element = stack.pop();
        if (!seen.contains(element)) {
            seen.add(element);
            tempStack.push(element);
        }
    }
    System.out.println("Time spent for idea2 is %d nanosecond".formatted(System.nanoTime() - start));
    return tempStack;
}

对于优化方法,我们使用

Set seen
存储Set中的唯一元素,在访问随机元素时利用O(1)复杂度来减少检查元素是否存在。

结合使用两种方法

以下是使用上述两种方法从给定堆栈中删除重复项的步骤 -

  • 初始化数据,我们使用initData(Long size)方法创建一个充满随机整数的堆栈。
  • 克隆堆栈我们使用 cloneStack(Stack stack) 方法 来创建原始堆栈的精确副本。
  • 使用initData.
  • 生成初始堆栈
  • 使用 cloneStack 克隆此堆栈。
  • 应用朴素方法从原始堆栈中删除重复项。
  • 应用优化方法从克隆堆栈中删除重复项。
  • 显示每种方法所花费的时间以及两种方法产生的独特元素

例子

下面是使用上述两种方法从堆栈中删除重复元素的 Java 程序 -

import java.util.HashSet;
import java.util.Random;
import java.util.Set;
import java.util.Stack;

public class DuplicateStackElements {
    private static Stack initData(Long size) {
        Stack stack = new Stack();
        Random random = new Random();
        int bound = (int) Math.ceil(size * 0.75);
        for (int i = 0; i  cloneStack(Stack stack) {
        Stack newStack = new Stack();
        newStack.addAll(stack);
        return newStack;
    }
    public static Stack idea1(Stack stack) {
        long start = System.nanoTime();
        Stack resultStack = new Stack();

        while (!stack.isEmpty()) {
            int element = stack.pop();
            if (!resultStack.contains(element)) {
                resultStack.add(element);
            }
        }
        System.out.printf("Time spent for idea1 is %d nanoseconds%n", System.nanoTime() - start);
        return resultStack;
    }
    public static Stack idea2(Stack stack) {
        long start = System.nanoTime();
        Set seen = new HashSet();
        Stack tempStack = new Stack();

        while (!stack.isEmpty()) {
            int element = stack.pop();
            if (!seen.contains(element)) {
                seen.add(element);
                tempStack.push(element);
            }
        }
        System.out.printf("Time spent for idea2 is %d nanoseconds%n", System.nanoTime() - start);
        return tempStack;
    }
    public static void main(String[] args) {
        Stack data1 = initData(10L);
        Stack data2 = cloneStack(data1);
        System.out.println("Unique elements using idea1: "   idea1(data1));
        System.out.println("Unique elements using idea2: "   idea2(data2));
    }
}

输出

Java program to remove duplicates from a given stack


比较

* 测量单位是纳秒。

public static void main(String[] args) {
    Stack data1 = initData();
    Stack data2 = manualCloneStack(data1);
    idea1(data1);
    idea2(data2);
}
方法 100 个元素 1000 个元素 10000 个元素
100000 个元素
1000000 个元素
想法1 693100
4051600
19026900
114201800
1157256000
想法2 135800
681400
2717800
11489400

36456100

据观察,想法 2 的运行时间比想法 1 短,因为想法 1 的复杂度为 O(n²),而想法 2 的复杂度为 O(n)。所以,当堆栈数量增加时,计算所花费的时间也会在此基础上增加。


版本声明 本文转载于:https://www.tutorialspoint.com/java-program-to-remove-duplicates-from-a-given-stack如有侵犯,请联系[email protected]删除
最新教程 更多>
  • 如何使用Python的请求和假用户代理绕过网站块?
    如何使用Python的请求和假用户代理绕过网站块?
    如何使用Python的请求模拟浏览器行为,以及伪造的用户代理提供了一个用户 - 代理标头一个有效方法是提供有效的用户式header,以提供有效的用户 - 设置,该标题可以通过browser和Acterner Systems the equestersystermery和操作系统。通过模仿像Chro...
    编程 发布于2025-07-18
  • 编译器报错“usr/bin/ld: cannot find -l”解决方法
    编译器报错“usr/bin/ld: cannot find -l”解决方法
    错误:“ usr/bin/ld:找不到-l “ 此错误表明链接器在链接您的可执行文件时无法找到指定的库。为了解决此问题,我们将深入研究如何指定库路径并将链接引导到正确位置的详细信息。添加库搜索路径的一个可能的原因是,此错误是您的makefile中缺少库搜索路径。要解决它,您可以在链接器命令中添加...
    编程 发布于2025-07-18
  • 如何在JavaScript对象中动态设置键?
    如何在JavaScript对象中动态设置键?
    在尝试为JavaScript对象创建动态键时,如何使用此Syntax jsObj['key' i] = 'example' 1;不工作。正确的方法采用方括号: jsobj ['key''i] ='example'1; 在JavaScript中,数组是一...
    编程 发布于2025-07-18
  • Java为何无法创建泛型数组?
    Java为何无法创建泛型数组?
    通用阵列创建错误 arrayList [2]; JAVA报告了“通用数组创建”错误。为什么不允许这样做?答案:Create an Auxiliary Class:public static ArrayList<myObject>[] a = new ArrayList<myO...
    编程 发布于2025-07-18
  • 为什么不````''{margin:0; }`始终删除CSS中的最高边距?
    为什么不````''{margin:0; }`始终删除CSS中的最高边距?
    在CSS 问题:不正确的代码: 全球范围将所有余量重置为零,如提供的代码所建议的,可能会导致意外的副作用。解决特定的保证金问题是更建议的。 例如,在提供的示例中,将以下代码添加到CSS中,将解决余量问题: body H1 { 保证金顶:-40px; } 此方法更精确,避免了由全局保证金重置引...
    编程 发布于2025-07-18
  • 如何使用Regex在PHP中有效地提取括号内的文本
    如何使用Regex在PHP中有效地提取括号内的文本
    php:在括号内提取文本在处理括号内的文本时,找到最有效的解决方案是必不可少的。一种方法是利用PHP的字符串操作函数,如下所示: 作为替代 $ text ='忽略除此之外的一切(text)'; preg_match('#((。 &&& [Regex使用模式来搜索特...
    编程 发布于2025-07-18
  • 左连接为何在右表WHERE子句过滤时像内连接?
    左连接为何在右表WHERE子句过滤时像内连接?
    左JOIN CONUNDRUM:WITCHING小时在数据库Wizard的领域中变成内在的加入很有趣,当将c.foobar条件放置在上面的Where子句中时,据说左联接似乎会转换为内部连接。仅当满足A.Foo和C.Foobar标准时,才会返回结果。为什么要变形?关键在于其中的子句。当左联接的右侧值...
    编程 发布于2025-07-18
  • Python环境变量的访问与管理方法
    Python环境变量的访问与管理方法
    Accessing Environment Variables in PythonTo access environment variables in Python, utilize the os.environ object, which represents a mapping of envir...
    编程 发布于2025-07-18
  • Python读取CSV文件UnicodeDecodeError终极解决方法
    Python读取CSV文件UnicodeDecodeError终极解决方法
    在试图使用已内置的CSV模块读取Python中时,CSV文件中的Unicode Decode Decode Decode Decode decode Error读取,您可能会遇到错误的错误:无法解码字节 在位置2-3中:截断\ uxxxxxxxx逃脱当CSV文件包含特殊字符或Unicode的路径逃...
    编程 发布于2025-07-18
  • 如何为PostgreSQL中的每个唯一标识符有效地检索最后一行?
    如何为PostgreSQL中的每个唯一标识符有效地检索最后一行?
    postgresql:为每个唯一标识符提取最后一行,在Postgresql中,您可能需要遇到与在数据库中的每个不同标识相关的信息中提取信息的情况。考虑以下数据:[ 1 2014-02-01 kjkj 在数据集中的每个唯一ID中检索最后一行的信息,您可以在操作员上使用Postgres的有效效率: ...
    编程 发布于2025-07-18
  • C++中如何将独占指针作为函数或构造函数参数传递?
    C++中如何将独占指针作为函数或构造函数参数传递?
    在构造函数和函数中将唯一的指数管理为参数 unique pointers( unique_ptr [2启示。通过值: base(std :: simelor_ptr n) :next(std :: move(n)){} 此方法将唯一指针的所有权转移到函数/对象。指针的内容被移至功能中,在操作...
    编程 发布于2025-07-18
  • 图片在Chrome中为何仍有边框?`border: none;`无效解决方案
    图片在Chrome中为何仍有边框?`border: none;`无效解决方案
    在chrome 在使用Chrome and IE9中的图像时遇到的一个频繁的问题是围绕图像的持续薄薄边框,尽管指定了图像,尽管指定了;和“边境:无;”在CSS中。要解决此问题,请考虑以下方法: Chrome具有忽略“ border:none; none;”的已知错误,风格。要解决此问题,请使用以下...
    编程 发布于2025-07-18
  • 您如何在Laravel Blade模板中定义变量?
    您如何在Laravel Blade模板中定义变量?
    在Laravel Blade模板中使用Elegance 在blade模板中如何分配变量对于存储以后使用的数据至关重要。在使用“ {{}}”分配变量的同时,它可能并不总是最优雅的解决方案。幸运的是,Blade通过@php Directive提供了更优雅的方法: $ old_section =“...
    编程 发布于2025-07-18
  • 如何简化PHP中的JSON解析以获取多维阵列?
    如何简化PHP中的JSON解析以获取多维阵列?
    php 试图在PHP中解析JSON数据的JSON可能具有挑战性,尤其是在处理多维数组时。 To simplify the process, it's recommended to parse the JSON as an array rather than an object.To do...
    编程 发布于2025-07-18
  • Python高效去除文本中HTML标签方法
    Python高效去除文本中HTML标签方法
    在Python中剥离HTML标签,以获取原始的文本表示Achieving Text-Only Extraction with Python's MLStripperTo streamline the stripping process, the Python standard librar...
    编程 发布于2025-07-18

免责声明: 提供的所有资源部分来自互联网,如果有侵犯您的版权或其他权益,请说明详细缘由并提供版权或权益证明然后发到邮箱:[email protected] 我们会第一时间内为您处理。

Copyright© 2022 湘ICP备2022001581号-3