我正在寻找一种方法来改变堆栈中元素的顺序,以便偶数位于奇数之后。
例如,以下堆栈:
5, 2, 6, 7, 1, 4, 3
变成:
5, 7, 1, 3, 2, 6, 4
这是我当前的代码。我一直在寻找如何更改订单:
public static void main(String[] args) {
Stack<Integer> p = new Stack<>();
p.push(3);
p.push(4);
p.push(1);
p.push(7);
p.push(6);
p.push(2);
p.push(5);
ListIterator<Integer> ListIterator = p.listIterator(p.size());
while (ListIterator.hasPrevious()) {
Integer i = ListIterator.previous();
System.out.println(i);
}
}
3条答案
按热度按时间ttp71kqs1#
有许多方法可以完成分离奇数和偶数元素的任务。
我怀疑这一挑战的目的是熟悉Stack data structure及其基本操作。
这里有一个解决方案,它利用两个额外的堆栈,一个用于累积奇数元素,另一个用于存储偶数元素。
初始堆栈被清空,其元素分布在其他两个堆栈之间。现在将奇数和偶数分开,剩下的唯一一件事就是连接数据。
该解的时间复杂度为线性O(n)。它比数据排序更高效,它将具有线性对数时间复杂度O(n log n)。
如何实施:
注:
Stack
类是遗留类,不应使用(除非您的任务要求)。当您需要在Java中实现堆栈数据结构时,建议使用Deque
接口的实现。p
更有意义的名称。这是一个好习惯,因为它使代码更易于阅读和维护。单字母变量仅在极少数情况下可接受,如for
循环中定义的变量。另见Java Language Naming Conventions。iq3niunx2#
Stack
是AbstractList
的子类,因此可以使用列表。通过提供自定义Comparator进行排序()。对于-
[3, 4, 1, 7, 6, 2, 5]
的初始堆栈,这将导致-[3, 1, 7, 5, 4, 6, 2]
。91zkwejq3#
比较模2之间的取反(因此
1
的阶数在0
之前)差:见live demo。