题目描述
这是 LeetCode 上的 950. 按递增顺序显示卡牌 ,难度为 中等。
牌组中的每张卡牌都对应有一个唯一的整数,你可以按你想要的顺序对这套卡片进行排序。
最初,这些卡牌在牌组里是正面朝下的(即未显示状态)。
现在,重复执行以下步骤,直到显示所有卡牌为止:
- 从牌组顶部抽一张牌,显示它,然后将其从牌组中移出。
- 如果牌组中仍有牌,则将下一张处于牌组顶部的牌放在牌组的底部。
- 如果仍有未显示的牌,那么返回步骤 1。否则,停止行动。
返回能以递增顺序显示卡牌的牌组顺序。
答案中的第一张牌被认为处于牌堆顶部。
示例:
| 输入:[17,13,11,2,3,5,7]
输出:[2,13,3,11,5,17,7]
解释: 我们得到的牌组顺序为 [17,13,11,2,3,5,7](这个顺序不重要),然后将其重新排序。 重新排序后,牌组以 [2,13,3,11,5,17,7] 开始,其中 2 位于牌组的顶部。 我们显示 2,然后将 13 移到底部。牌组现在是 [3,11,5,17,7,13]。 我们显示 3,并将 11 移到底部。牌组现在是 [5,17,7,13,11]。 我们显示 5,然后将 17 移到底部。牌组现在是 [7,13,11,17]。 我们显示 7,并将 13 移到底部。牌组现在是 [11,17,13]。 我们显示 11,然后将 17 移到底部。牌组现在是 [13,17]。 我们展示 13,然后将 17 移到底部。牌组现在是 [17]。 我们显示 17。 由于所有卡片都是按递增顺序排列显示的,所以答案是正确的。
|
提示:
- $1 <= A.length <= 1000$
- $1 <= A[i] <= 10^6$
- 对于所有的
i != j
,A[i] != A[j]
模拟
根据题意,我们可以先使用双端队列对 deck
进行一次模拟,并用哈希表记下每个元素 $deck[i]$ 的显示顺序(利用 $deck[i]$ 元素各不相同,可直接用 $deck[i]$ 作为 key
)。
随后考虑如何通过哈希表来构建答案数组 ans
。
假设原数组中的 $deck[i]$ 为首次显示的卡牌,那么 $ans[i]$ 应该放置 deck
中最小的元素,同理若 $deck[j]$ 若最后显示的卡牌,则 $ans[j]$ 应放置 deck
中的最大元素。
为了方便找 deck
中第 $k$ 大元素,可对 deck
进行拷贝并排序。
Java 代码:
| class Solution { public int[] deckRevealedIncreasing(int[] deck) { int n = deck.length, idx = 0; Map<Integer, Integer> map = new HashMap<>(); Deque<Integer> d = new ArrayDeque<>(); for (int x : deck) d.addLast(x); while (!d.isEmpty()) { map.put(d.pollFirst(), idx++); if (!d.isEmpty()) d.addLast(d.pollFirst()); } int[] ans = new int[n], temp = deck.clone(); Arrays.sort(temp); for (int i = 0; i < n; i++) ans[i] = temp[map.get(deck[i])]; return ans; } }
|
C++ 代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| class Solution { public: vector<int> deckRevealedIncreasing(vector<int>& deck) { int n = deck.size(), idx = 0; map<int, int> map; deque<int> d; for (int x : deck) d.push_back(x); while (!d.empty()) { map[d.front()] = idx++; d.pop_front(); if (!d.empty()) { d.push_back(d.front()); d.pop_front(); } } vector<int> ans(n); vector<int> temp = deck; sort(temp.begin(), temp.end()); for (int i = 0; i < n; i++) ans[i] = temp[map[deck[i]]]; return ans; } };
|
Python3 代码:
| class Solution: def deckRevealedIncreasing(self, deck: List[int]) -> List[int]: n, idx = len(deck), 0 map = {} d = deque(deck) while d: map[d.popleft()] = idx idx += 1 if d: d.append(d.popleft()) temp = sorted(deck) return [temp[map[deck[i]]] for i in range(n)]
|
TypeScript 代码:
| function deckRevealedIncreasing(deck: number[]): number[] { let n = deck.length, idx = 0; const map = {}; const d = [...deck]; while (d.length > 0) { map[d.shift()!] = idx++; if (d.length > 0) d.push(d.shift()!); } const ans = new Array(n); const temp = [...deck].sort((a, b) => a - b); for (let i = 0; i < n; i++) ans[i] = temp[map[deck[i]]]; return ans; };
|
- 时间复杂度:使用队列模拟一次操作的复杂度为 $O(n)$(每个元素只有一次出入队机会);对原数组进行复制并排序的复杂度 $O(n\log{n})$;构建答案复杂度为 $O(n)$。整体复杂度为 $O(n\log{n})$
- 空间复杂度:$O(n)$
最后
这是我们「刷穿 LeetCode」系列文章的第 No.950
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。