某大厂员工爆料，加班后在工位很晕，天旋地转，出公司差点摔倒，回家一量血压高达150！

刚看到个贴子，说某大厂有同学加完班直接在工位上头晕到天旋地转，走出公司差点摔倒，回家一量血压飙到150，属实吓人一跳。

网友们回复也挺激烈，有的说大厂强度本来就高，有的怪当事人不懂得自我保护。但在我看来，甭管公司节奏多快，健康这根弦一松，后面啥都白搭。

人不是机器，晕到站不稳这种信号已经是身体在“亮红灯”了。这时候再硬扛，只会把小问题拖成大毛病。

我比较认同网友里一句话：工作可以替代，身体没得换。尤其是现在大家都讲性价比，你把自己累到血压飙升，这性价比也太低了。

该休息就休息，该拒绝的活儿要学会拒绝，不然最后谁都帮不了你。

赚钱重要，但身体更重要。工作丢了还能找，身体垮了就真的不划算了。【备注:文末可领最新资料】

面试题：寻找数组的错位排列

想象一下，你有一个数组：

int[] nums = {1, 2, 3};

正常的全排列，比如 [1,2,3]、[2,1,3]、[3,2,1] 这些都算排列。

但“错位排列”有个额外要求：每个位置上的数字，不能和原数组这个位置一样。也就是说：

• 原数组第 0 个位置是 1，那错位排列的第 0 个位置就不能是 1
• 第 1 个位置原来是 2，那错位后第 1 个位置就不能是 2
• 第 2 个位置原来是 3，那错位后第 2 个位置就不能是 3

所以，对 {1,2,3} 来说：

• [2,3,1]：OK，0 位不是 1，1 位不是 2，2 位不是 3，全错开了
• [3,1,2]：也 OK
• [1,3,2]：不行，因为第 0 位还是 1 这种“每个元素都不在原来的位置上”的排列，就叫错位排列（derangement）。

我们的题目就是：给你一个数组，把所有错位排列都找出来。

正常全排列怎么搞？一般就是回溯嘛，一层一层往下选：

• 第 0 个位置选一个没用过的数
• 第 1 个位置再选一个没用过的数
• ...
• 选满 n 个位置，得到一个排列

那现在多了个条件： 在第 i 个位置选数的时候，这个数不能等于原数组 nums[i]。

所以回溯的时候，加一行判断就行了：

• 这个数没用过
• 并且这个数 ≠ nums[当前位置]

满足这俩条件才能选。

整体就是：

1. 用一个 boolean[] used 标记某个下标的元素有没有被用过

2. 用一个 List<Integer> path 表示当前已经选好的排列前缀

3. 递归下去填位置 index，从 0 到 nums.length - 1

4. 填第 index 个位置的时候，枚举 nums 里所有元素，看哪个能放：

• !used[j]（还没用）
• nums[j] != nums[index]（不能和原来这个位置一样）

直接上可跑的代码，你看着就能明白：

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

publicclassDerangementFinder{

// 对外暴露的入口方法
publicstatic List<int[]> findDerangements(int[] nums) {
        List<int[]> res = new ArrayList<>();
boolean[] used = newboolean[nums.length];
        List<Integer> path = new ArrayList<>();
        backtrack(nums, 0, used, path, res);
return res;
    }

// 回溯核心
privatestaticvoidbacktrack(int[] nums,
int index,           // 当前要填的位置
boolean[] used,      // 哪些元素已经被用过
                                  List<Integer> path,  // 当前构建中的排列
                                  List<int[]> res){   // 结果集
// 填满了一个排列
if (index == nums.length) {
int[] arr = newint[nums.length];
for (int i = 0; i < nums.length; i++) {
                arr[i] = path.get(i);
            }
            res.add(arr);
return;
        }

// 尝试把 nums[j] 放到 index 位置
for (int j = 0; j < nums.length; j++) {
// 已经用过，跳过
if (used[j]) {
continue;
            }
// 不能和原数组这个位置一样，否则就没“错位”了
if (nums[j] == nums[index]) {
continue;
            }

// 选择 nums[j]
            used[j] = true;
            path.add(nums[j]);

// 递归填下一个位置
            backtrack(nums, index + 1, used, path, res);

// 回溯撤销选择
            path.remove(path.size() - 1);
            used[j] = false;
        }
    }

// 简单测一下
publicstaticvoidmain(String[] args){
int[] nums = {1, 2, 3};
        List<int[]> res = findDerangements(nums);
for (int[] arr : res) {
            System.out.println(Arrays.toString(arr));
        }
    }
}

如果你用 {1,2,3} 跑一下，打印出来的会是：

[2, 3, 1]
[3, 1, 2]

这俩刚好就是 {1,2,3} 的所有错位排列。

这个问题本质上还是全排列，所以时间复杂度差不多是 O(n!)，只是多了一点剪枝（那些本来就等于原位置的选择直接跳过了）。所以这个方法适合 n 比较小的情况，比如 n ≤ 10 这种，用来刷题、面试都够用了。

还有几个小点你可以记一下：

• 一定要按“位置”来判断错位，而不是按“下标等不等于值”这种偷懒写法，因为数组不一定是 1..n 那种
• 用 used[] 而不是每次 path.contains，否则性能会比较差
• 返回结果的时候，用 int[] 拷贝一份出来，别直接保存 path，不然后面回溯一改，全变了

如果你想再扩展一下，这个错位排列还能拿去做组合数学的小题，比如算“总共有多少个错位排列”，那就是经典的公式题了，代码这里就先不塞了，怕超字数 😂

你先把这个写熟，后面想玩点花样（比如只输出一个、只统计个数、加更多限制）都可以在这个回溯框架上改。

-END-

我为大家打造了一份RPA教程，完全免费：songshuhezi.com/rpa.html