950. Reveal Cards In Increasing Order

 1import java.util.Arrays;
 2import java.util.LinkedList;
 3import java.util.Queue;
 4
 5/**
 6 * @author lxn
 7 * @description 950. Reveal Cards In Increasing Order
 8 * @create 2020-02-13 17:28
 9 */
10public class Algorithm950 {
11    public static void main(String[] args) {
12        int[] deck = {17, 13, 11, 2, 3, 5, 7};
13        int[] res = new Solution950().deckRevealedIncreasing(deck);
14    }
15}
16
17class Solution950 {
18    public int[] deckRevealedIncreasing(int[] deck) {
19        int[] tmp = new int[deck.length];
20        Queue<Integer> queue = new LinkedList<>();
21        // 把deck的index按顺序放进队列
22        for(int i = 0; i < deck.length; i++){
23            queue.offer(i); // 加入元素
24        }
25        int count = 0; // 用来记录tmp到第几个index
26        // 注意：因为Queue里放的是index，所以永远都是0,1,...,deck.length-1这些数，和原数组deck的元素无关。这里虽然还没有排序，但得到的indexes其实是排序后的数组有关。
27        // 也就是说无论deck存的什么元素(只要唯一)，只要deck的长度相同，得到的tmp都是一样的。但如果一个deck的长度为3，一个长度为5，但长度为5得到的tmp的前三位并不等于长度为3的deck。
28        for(int i = 0; queue.size() > 0; i++){
29            if(i % 2 == 0){ // 偶数
30                tmp[count++] = queue.poll();// queue先弹出0，然后是2, 4, 6, 3, 1, 5 这些数在队列里也没有了
31            }else{ // 奇数
32                queue.offer(queue.poll());// 一开始queue.poll()是1，然后在末尾加入1; 然后是3, 5, 1, 5, 5。这些元素用完还留在队列里
33            }
34        }
35        Arrays.sort(deck); // 将deck从小到大排序
36        int[] res = new int[deck.length];
37        // tmp = {0, 2, 4, 6, 3, 1, 5}
38        for(int i = 0; i < deck.length; i++){
39            res[tmp[i]] = deck[i]; // tmp的值当index
40        }
41        return res;
42    }
43}