每日一题——有重复项数字的全排列

题目

给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。

数据范围：

• $0<n\le 8$
• 数组中的值满足 $-1\le val\le 5$

要求：

• 空间复杂度 $O(n!)$
• 时间复杂度 $O(n!)$

示例

示例 1
输入：

[1,1,2]

返回值：

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

示例 2
输入：

[0,1]

返回值：

[[0,1], [1,0]]

题解

思路

本题的核心在于生成一个数组的全排列，并且需要去除重复的排列。由于输入数组可能包含重复的元素，因此直接通过传统的全排列方法会产生重复结果，需要避免这种情况。

我们可以通过回溯算法来解决这个问题，回溯算法的基本思想是通过逐步选择元素并在选择完成后撤销选择（回退），这样我们能够生成所有的排列。为了去除重复项，可以在每次选择时判断当前元素是否与前一个元素相同，并且前一个元素没有被使用过，如果是这种情况则跳过该元素，避免生成重复排列。

详细步骤

1. 排序：首先对数组进行排序，以便于后面判断重复项。
2. 回溯：使用回溯算法生成所有可能的排列。在回溯的过程中，对于已经选择过的元素，通过一个标记数组 used 来记录其是否被选择过。
3. 去重：在回溯中，对于相同的元素，只有在前一个元素没有被使用的情况下，才能选择当前元素，避免生成重复排列。

代码实现

#include <stdio.h>
#include <stdlib.h>

// 回溯函数：生成全排列
void backtrack(int* num, int numLen, int** result, int* returnSize,int* returnColumnSizes, int* current, int currentLen, int* used) {
    // 如果当前排列长度等于数字长度，说明一个排列已生成
    if (currentLen == numLen) {
        // 为当前排列分配内存
        result[*returnSize] = (int*)malloc(sizeof(int) * numLen);
        // 将当前排列复制到结果数组中
        for (int i = 0; i < numLen; i++) {
            result[*returnSize][i] = current[i];
        }
        // 设置当前排列的列大小
        returnColumnSizes[*returnSize] = numLen;
        // 增加返回结果的大小
        (*returnSize)++;
        return;
    }

    // 遍历每个数字，尝试放入当前排列中
    for (int i = 0; i < numLen; i++) {
        // 如果该元素没有被使用或存在重复元素且前一个元素没有被使用
        if (used[i] == 1 || (i > 0 && used[i-1] == 0 && num[i] == num[i-1])) {
            continue;
        }

        // 标记该元素已使用
        used[i] = 1;
        // 将该元素加入当前排列
        current[currentLen] = num[i];
        // 递归调用，继续选择下一个元素
        backtrack(num, numLen, result, returnSize, returnColumnSizes, current, currentLen + 1, used);
        // 回溯，撤销选择
        used[i] = 0;
    }
}

// 排序函数：用来排序输入数组
void sort(int* num, int numLen) {
    for (int i = 0; i < numLen - 1; i++) {
        for (int j = 0; j < numLen - i - 1; j++) {
            if (num[j] > num[j+1]) {
                int temp = num[j];
                num[j] = num[j+1];
                num[j+1] = temp;
            }
        }
    }
}

// permute函数，生成所有排列
int** permuteUnique(int* num, int numLen, int* returnSize, int** returnColumnSizes) {
    // 排序输入数组，确保相同数字连续
    sort(num, numLen);
    
    // 预分配空间，最多有10000个排列
    int** result = (int**)malloc(sizeof(int*) * 10000);
    
    // 预分配列大小空间
    *returnColumnSizes = (int*)malloc(sizeof(int) * 10000);
    
    // 初始化返回结果的大小为0
    *returnSize = 0;
    
    // 用于保存当前排列
    int* current = (int*)malloc(sizeof(int) * numLen);
    
    // 用于标记哪些元素已经使用，初始化为0
    int* used = (int*)calloc(numLen, sizeof(int));
    
    // 调用回溯生成排列
    backtrack(num, numLen, result, returnSize, *returnColumnSizes, current, 0, used);
    
    // 释放临时数组
    free(current);
    free(used);
    
    // 返回结果数组
    return result;
}

代码解释

1. 排序：在开始回溯之前，我们对输入数组进行了排序，目的是为了保证相同的数字会被放在相邻位置，便于去重。
2. 回溯：backtrack 函数是生成排列的核心。每次选择一个数字，如果该数字已经被使用或者是重复的数字（且前一个数字没有被使用），则跳过这个数字。
3. 去重：通过判断 used[i-1] == 0 && num[i] == num[i-1] 来避免选择重复的元素。

时间复杂度

由于需要生成所有排列，因此时间复杂度为 $O(n!)$，其中 $n$ 是输入数组的长度。

空间复杂度

空间复杂度也是 $O(n!)$，因为我们需要存储所有可能的排列。

总结

本题通过回溯算法和去重策略解决了具有重复数字的全排列问题。通过递归的方式生成排列并利用排序确保生成的排列按字典序排列，最终返回去重后的结果。
本题最难的还是去重逻辑，多的冒泡排序还是很容意的，通过判断 used[i-1] == 0 && num[i] == num[i-1]。实际上分为两种情况，一种情况used[i] == 1 ，说明之前已经被选择了，直接跳过，另一种情况used[i] == 0 ，这时候由于或逻辑，可以省略， (i > 0 &&num[i] == num[i-1]&& used[i-1] == 0 )，先让i > 0 ，防止num[i-1]越界，used[i-1] == 0，说明前一个相同的元素在当前层还没有被使用过。这意味着如果当前元素被选择，那么前一个相同的元素也会在后续的递归中被选择，从而导致重复排列。我的理解，要是在一层中有多个相同的值，那么只有第一个可以在本层被选择 num[i] != num[i-1]&& used[i-1] == 0.