ID: 830

Difficulty: 4

所属公司 : 美团

时间 :2024年3月23日

题目描述

小美有一个排列，所有元素为红色或者白色。

哈希表 + 模拟

受到题目41. 缺失的第一个正数的启发：

因为最终一定是第i个位置要是i。所以我们不妨从左往右扫描。遇到第一个不是 $i$ 的，我们就和当前 $i$ 所在的位置进行交换。

而找到 $i$ 所在的位置就是使用哈希表来记录每个元素所在的下标。然后模拟交换即可

python