README.md

comments	difficulty	edit_url	tags
true	中等	https://github.com/doocs/leetcode/edit/main/solution/3200-3299/3237.Alt%20and%20Tab%20Simulation/README.md	数组 哈希表 模拟

3237. Alt 和 Tab 模拟 🔒

English Version

题目描述

有 n 个编号从  1 到 n 的打开的窗口，我们想要模拟使用 alt + tab 键在窗口之间导航。

给定数组 windows 包含窗口的初始顺序（第一个元素在最前面，最后一个元素在最后面）。

同时给定数组 queries 表示每一次查询中，编号为 queries[i] 的窗口被切换到最前面。

返回 windows 数组的最后状态。

 

示例 1：

输入：windows = [1,2,3], queries = [3,3,2]

输出：[2,3,1]

解释：

以下是每次查询后的 windows 数组：

• 初始顺序：[1,2,3]
• 第一次查询后：[3,1,2]
• 第二次查询后：[3,1,2]
• 最后一次查询后：[2,3,1]

示例 2:

输入：windows = [1,4,2,3], queries = [4,1,3]

输出：[3,1,4,2]

解释：

以下是每次查询后的 windows 数组：

• 初始顺序：[1,4,2,3]
• 第一次查询后：[4,1,2,3]
• 第二次查询后：[1,4,2,3]
• 最后一次查询后：[3,1,4,2]

 

提示：

• 1 <= n == windows.length <= 105
• windows 是 [1, n] 的一个排列。
• 1 <= queries.length <= 105
• 1 <= queries[i] <= n

解法

方法一：哈希表 + 逆序遍历

根据题目描述，越是后面的查询，越是出现在最前面的位置。因此，我们可以逆序遍历 $\textit{queries}$ 数组，用一个哈希表 $\textit{s}$ 记录已经出现过的窗口。对于每一个查询，如果当前窗口不在哈希表中，我们将其加入答案数组，并将其加入哈希表中。最后，我们再次遍历 $\textit{windows}$ 数组，将不在哈希表中的窗口加入答案数组。

时间复杂度 $O(n + m)$，空间复杂度 $O(m)$。其中 $n$ 和 $m$ 分别为 $\textit{windows}$ 和 $\textit{queries}$ 数组的长度。

Python3

class Solution:
    def simulationResult(self, windows: List[int], queries: List[int]) -> List[int]:
        s = set()
        ans = []
        for q in queries[::-1]:
            if q not in s:
                ans.append(q)
                s.add(q)
        for w in windows:
            if w not in s:
                ans.append(w)
        return ans

Java

class Solution {
    public int[] simulationResult(int[] windows, int[] queries) {
        int n = windows.length;
        boolean[] s = new boolean[n + 1];
        int[] ans = new int[n];
        int k = 0;
        for (int i = queries.length - 1; i >= 0; --i) {
            int q = queries[i];
            if (!s[q]) {
                ans[k++] = q;
                s[q] = true;
            }
        }
        for (int w : windows) {
            if (!s[w]) {
                ans[k++] = w;
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    vector<int> simulationResult(vector<int>& windows, vector<int>& queries) {
        int n = windows.size();
        vector<bool> s(n + 1);
        vector<int> ans;
        for (int i = queries.size() - 1; ~i; --i) {
            int q = queries[i];
            if (!s[q]) {
                s[q] = true;
                ans.push_back(q);
            }
        }
        for (int w : windows) {
            if (!s[w]) {
                ans.push_back(w);
            }
        }
        return ans;
    }
};

Go

func simulationResult(windows []int, queries []int) (ans []int) {
	n := len(windows)
	s := make([]bool, n+1)
	for i := len(queries) - 1; i >= 0; i-- {
		q := queries[i]
		if !s[q] {
			s[q] = true
			ans = append(ans, q)
		}
	}
	for _, w := range windows {
		if !s[w] {
			ans = append(ans, w)
		}
	}
	return
}

TypeScript

function simulationResult(windows: number[], queries: number[]): number[] {
    const n = windows.length;
    const s: boolean[] = Array(n + 1).fill(false);
    const ans: number[] = [];
    for (let i = queries.length - 1; i >= 0; i--) {
        const q = queries[i];
        if (!s[q]) {
            s[q] = true;
            ans.push(q);
        }
    }
    for (const w of windows) {
        if (!s[w]) {
            ans.push(w);
        }
    }
    return ans;
}