当前位置：首页 > article >正文

LeetCode 2475 数组中不等三元组的数目

article 2025/1/23 9:06:18

问题描述:

给定一个下标从 0 开始的正整数数组 nums，我们的目标是找出并统计满足下述条件的三元组 (i, j, k) 的数目：

0 <= i < j < k < nums.length，这确保了三元组索引的顺序性。
nums[i]、nums[j] 和 nums[k] 两两不同，即 nums[i]!= nums[j]、nums[i]!= nums[k] 且 nums[j]!= nums[k]。

暴力解法 - 三层循环遍历

最直观的解法就是使用三层嵌套循环来遍历数组的所有可能组合

#include <stdio.h>

// 函数定义，用于找出满足条件的三元组数量
int unequalTriplets(int* nums, int numsSize) {
    int count = 0;
    for (int i = 0; i < numsSize - 2; i++) {
        for (int j = i + 1; j < numsSize - 1; j++) {
            for (int k = j + 1; k < numsSize; k++) {
                if (nums[i]!= nums[j] && nums[i]!= nums[k] && nums[j]!= nums[k]) {
                    count++;
                }
            }
        }
    }
    return count;
}

int main() {
    int nums[] = {1, 2, 3, 4};  // 示例数组，你可以替换成其他测试数组
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int result = unequalTriplets(nums, numsSize);
    printf("满足条件的三元组数目为: %d\n", result);
    return 0;
}

在这段代码中：

最外层循环控制第一个索引 i，它从数组起始位置开始，一直到倒数第 3 个位置（因为后面还需要留出 j 和 k 的位置）。
中间层循环控制第二个索引 j，它从 i + 1 开始，确保 j > i，到倒数第 2 个位置。
最内层循环控制第三个索引 k，从 j + 1 开始，保证 k > j，直到数组末尾。
在内层循环里，每次都检查当前的三个元素是否两两不等，如果是，就将计数变量 count 加 1。最终，count 存储的就是满足条件的三元组数量。

这种解法简单直接，但时间复杂度高达 $o(n^{3})$ ，其中 n 是数组 nums 的长度。在大规模数据面前，性能会急剧下降。

优化解法 - 计数与组合数学原理

为了提升效率，我们可以换个思路。先统计数组中每个数字出现的频次，再利用组合数学的原理来计算满足条件的三元组数量。

#include <stdio.h>

// 函数定义，用于找出满足条件的三元组数量
int unequalTriplets(int* nums, int numsSize) {
    int count = 0;
    // 用于记录每个数字出现的次数
    int num_count[1001] = {0};
    for (int i = 0; i < numsSize; i++) {
        num_count[nums[i]]++;
    }
    int left = 0;
    int right = numsSize;
    for (int i = 0; i < 1001; i++) {
        if (num_count[i] > 0) {
            right -= num_count[i];
            count += left * num_count[i] * right;
            left += num_count[i];
        }
    }
    return count;
}

int main() {
    int nums[] = {1, 2, 3, 4};  // 示例数组，你可以替换成其他测试数组
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int result = unequalTriplets(nums, numsSize);
    printf("满足条件的三元组数目为: %d\n", result);
    return 0;
}

首先，创建一个大小为 1001 的数组 num_count（假设数组中的数字最大不超过 1000，可根据实际情况调整），用于记录每个数字在 nums 数组里出现的频次。通过一次遍历 nums 数组，将每个数字对应的频次在 num_count 中累加。
接着，使用两个变量 left 和 right。left 初始化为 0，表示当前数字左边不同数字的个数；right 初始化为数组长度 numsSize，代表当前数字右边不同数字的个数。
遍历 num_count 数组时，每当遇到一个数字出现次数不为 0：
- 先更新 right，将其减去当前数字的出现次数，因为这些数字已经被算到当前位置左边或当前位置了，不能再算在右边。
- 根据组合数学原理，当前数字与左边不同数字和右边不同数字能组成的满足条件三元组数量为 left * num_count[i] * right，累加到 count 中。
- 最后更新 left，将当前数字的出现次数累加到 left 上，准备处理下一个数字。