問(wèn)題描述:? ? ? ? ? ? ?

給定一個(gè)下標(biāo)從 0 開(kāi)始的正整數(shù)數(shù)組?nums，我們的目標(biāo)是找出并統(tǒng)計(jì)滿足下述條件的三元組?(i, j, k)?的數(shù)目：

1. 0 <= i < j < k < nums.length，這確保了三元組索引的順序性。
2. nums[i]、nums[j]?和?nums[k]?兩兩不同，即?nums[i]!= nums[j]、nums[i]!= nums[k]?且?nums[j]!= nums[k]。

暴力解法 - 三層循環(huán)遍歷

最直觀的解法就是使用三層嵌套循環(huán)來(lái)遍歷數(shù)組的所有可能組合

#include <stdio.h>// 函數(shù)定義，用于找出滿足條件的三元組數(shù)量
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};  // 示例數(shù)組，你可以替換成其他測(cè)試數(shù)組int numsSize = sizeof(nums) / sizeof(nums[0]);int result = unequalTriplets(nums, numsSize);printf("滿足條件的三元組數(shù)目為: %d\n", result);return 0;
}

在這段代碼中：

• 最外層循環(huán)控制第一個(gè)索引?i，它從數(shù)組起始位置開(kāi)始，一直到倒數(shù)第 3 個(gè)位置（因?yàn)楹竺孢€需要留出?j?和?k?的位置）。
• 中間層循環(huán)控制第二個(gè)索引?j，它從?i + 1?開(kāi)始，確保?j > i，到倒數(shù)第 2 個(gè)位置。
• 最內(nèi)層循環(huán)控制第三個(gè)索引?k，從?j + 1?開(kāi)始，保證?k > j，直到數(shù)組末尾。
• 在內(nèi)層循環(huán)里，每次都檢查當(dāng)前的三個(gè)元素是否兩兩不等，如果是，就將計(jì)數(shù)變量?count?加 1。最終，count?存儲(chǔ)的就是滿足條件的三元組數(shù)量。

這種解法簡(jiǎn)單直接，但時(shí)間復(fù)雜度高達(dá)?，其中?n?是數(shù)組?nums?的長(zhǎng)度。在大規(guī)模數(shù)據(jù)面前，性能會(huì)急劇下降。

優(yōu)化解法 - 計(jì)數(shù)與組合數(shù)學(xué)原理

為了提升效率，我們可以換個(gè)思路。先統(tǒng)計(jì)數(shù)組中每個(gè)數(shù)字出現(xiàn)的頻次，再利用組合數(shù)學(xué)的原理來(lái)計(jì)算滿足條件的三元組數(shù)量。

#include <stdio.h>// 函數(shù)定義，用于找出滿足條件的三元組數(shù)量
int unequalTriplets(int* nums, int numsSize) {int count = 0;// 用于記錄每個(gè)數(shù)字出現(xiàn)的次數(shù)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};  // 示例數(shù)組，你可以替換成其他測(cè)試數(shù)組int numsSize = sizeof(nums) / sizeof(nums[0]);int result = unequalTriplets(nums, numsSize);printf("滿足條件的三元組數(shù)目為: %d\n", result);return 0;
}

• 首先，創(chuàng)建一個(gè)大小為?1001?的數(shù)組?num_count（假設(shè)數(shù)組中的數(shù)字最大不超過(guò)?1000，可根據(jù)實(shí)際情況調(diào)整），用于記錄每個(gè)數(shù)字在?nums?數(shù)組里出現(xiàn)的頻次。通過(guò)一次遍歷?nums?數(shù)組，將每個(gè)數(shù)字對(duì)應(yīng)的頻次在?num_count?中累加。
• 接著，使用兩個(gè)變量?left?和?right。left?初始化為 0，表示當(dāng)前數(shù)字左邊不同數(shù)字的個(gè)數(shù)；right?初始化為數(shù)組長(zhǎng)度?numsSize，代表當(dāng)前數(shù)字右邊不同數(shù)字的個(gè)數(shù)。
• 遍歷?num_count?數(shù)組時(shí)，每當(dāng)遇到一個(gè)數(shù)字出現(xiàn)次數(shù)不為 0：
  • 先更新?right，將其減去當(dāng)前數(shù)字的出現(xiàn)次數(shù)，因?yàn)檫@些數(shù)字已經(jīng)被算到當(dāng)前位置左邊或當(dāng)前位置了，不能再算在右邊。
  • 根據(jù)組合數(shù)學(xué)原理，當(dāng)前數(shù)字與左邊不同數(shù)字和右邊不同數(shù)字能組成的滿足條件三元組數(shù)量為?left * num_count[i] * right，累加到?count?中。
  • 最后更新?left，將當(dāng)前數(shù)字的出現(xiàn)次數(shù)累加到?left?上，準(zhǔn)備處理下一個(gè)數(shù)字。

這種優(yōu)化后的解法時(shí)間復(fù)雜度降低到?，其中?n?是數(shù)組?nums?的長(zhǎng)度，m?是數(shù)組中不同數(shù)字的個(gè)數(shù)。相比暴力解法，大大提高了計(jì)算效率。

總結(jié)與拓展:

從簡(jiǎn)單直接但低效的暴力解法，到巧妙利用數(shù)據(jù)統(tǒng)計(jì)和數(shù)學(xué)原理的高效解法，效率得到了質(zhì)的飛躍。在實(shí)際編程中，面對(duì)類(lèi)似問(wèn)題，我們應(yīng)多思考數(shù)據(jù)的內(nèi)在規(guī)律，嘗試從不同角度去拆解問(wèn)題，運(yùn)用合適的數(shù)學(xué)知識(shí)或數(shù)據(jù)結(jié)構(gòu)來(lái)優(yōu)化算法。

希望通過(guò)這篇博客，大家對(duì)數(shù)組計(jì)數(shù)類(lèi)算法問(wèn)題有了更清晰的理解，也能在日后的編程實(shí)踐中靈活運(yùn)用這些思路去攻克難題。

?