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

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

问题陈述

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

输入

雷雷

输出

雷雷

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

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

生成和克隆随机堆栈

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

雷雷

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

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

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

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

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

示例

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

雷雷

对于朴素的方法，我们使用

Stack<Integer> data = initData(10L);

处理第一个循环，遍历堆栈中的所有元素，第二个循环 <div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:php;toolbar:false">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</pre><div class="contentsignin">登录后复制</div></div> 检查该元素是否已经存在。

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

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

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

示例

下面是使用 HashSet 从给定堆栈中删除重复项的 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 < size; ++i) {
        stack.add(random.nextInt(bound) + 1);
    }
    return stack;
}

private static Stack < Integer > manualCloneStack(Stack < Integer > stack) {
    Stack < Integer > newStack = new Stack < > ();
    for (Integer item: stack) {
        newStack.push(item);
    }
    return newStack;
}

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

同时使用这两种方法

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

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

示例

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

雷雷

输出

比较

* 测量单位是纳秒。

public static void main(String[] args) {
    Stack<Integer> data1 = initData(<number of stack size want to test>);
    Stack<Integer> data2 = manualCloneStack(data1);
    idea1(data1);
    idea2(data2);
}

Method	100 elements	1000 elements	10000 elements	100000 elements	1000000 elements
Idea 1	693100	4051600	19026900	114201800	1157256000
Idea 2	135800	681400	2717800	11489400	36456100

As observed, the time running for Idea 2 is shorter than for Idea 1 because the complexity of Idea 1 is O(n²), while the complexity of Idea 2 is O(n). So, when the number of stacks increases, the time spent on calculations also increases based on it.

---

以上是Java程序从给定堆栈中删除重复项的详细内容。更多信息请关注PHP中文网其他相关文章！