java - 重新排列整数队列

Question

我试图编写一种方法，可以将整数队列从偶数重新排列为奇数。

这样 [3, 5, 4, 17, 6, 83, 1, 84, 16, 37] 将类似于 [4, 6, 84, 16, 3, 5, 17, 83, 1, 37]

但我现在有点卡住了，有人可以帮助我吗？这是我到目前为止得到的

public void rearrange(Queue<Integer> q) {
    Stack<Integer> s = new Stack<Integer>();
    int size = q.size();
for (int i = 0; i < size; i++) {
    int n = q.remove();
    if (n % 2 == 1 || n % 2 == -1) {
        q.add(n);
    } 

    if( n % 2 == 0) {
        q.add(n);
    }
}
}

Answer 1

创建一个临时队列（或列表）。遍历主队列，删除奇数元素并将它们放入临时队列。最后将所有列表元素添加到主队列

Answer 2

排序没问题，但它需要 O(n log n) 时间，而你可以很容易地在 O(n) 中做到这一点。我认为这也是 Evgeniy Dorofeev 提出的：

public static void rearrange(Queue<Integer> q) {
    Queue<Integer> tmp = new LinkedList<>();

    // Remember size and rearrange that many items.
    int size = q.size();

    for (int count = 0; count < size; count++) {
        Integer head = q.poll();

        // Even items go on the end of the original queue, odd to temp.
        (head % 2 == 0 ? q : tmp).offer(head);
    }
    // Glue temp queue of odd values onto original which is all even.
    q.addAll(tmp);
}

Answer 3

JavaComparator正是为了这种事情。把它们放在一个java.util.List. 编写一个比较器，例如：

class OddEvenComparator implements Comparator<Integer> {
  public int compare (Integer a, Integer b) {
    boolean aOdd = (a % 2) != 0;
    boolean bOdd = (b % 2) != 0;
    return aOdd == bOdd ? a.compareTo(b) : aOdd ? -1 : 1;
  }
}

以便

• 如果它们都是奇数或偶数，则比较它们的值
• 如果 a 是奇数而 b 不是，它的位置向后移动
• 如果 a 是偶数而 b 不是，它的位置向前移动

用来Collections.sort(theList, new OddEvenComparator())排序。