C語言實作：計算兩陣列支配值數目（num[] 中大於 cou[] 的配對數）

陣列配對比較：支配值計數

給定兩個等長陣列 num[] 與 cou[]，計算有多少個配對 (i, j) 使得 num[j] > cou[i]。本質上是計算兩陣列所有元素兩兩比較中，第一個陣列元素大於第二個陣列元素的次數。

問題描述

陣列 num[] = {1, 3, 5, 7, 9}，cou[] = {2, 3, 4, 7, 8}。
雙重迴圈比較所有 5×5=25 種配對，計算滿足 num[j] > cou[i] 的總數。

程式碼實作

#include <stdio.h>

int main()
{
    int i, j, count = 0;
    int num[] = {1, 3, 5, 7, 9};
    int cou[] = {2, 3, 4, 7, 8};

    for(i = 0; i < 5; i++)
    {
        for(j = 0; j < 5; j++)
        {
            if(num[j] > cou[i]) count++;
        }
    }

    printf("陣列num[]比陣列cou[]大的數有%d個\n", count);
    return 0;
}

手動驗證

程式輸出應為 12。

最佳化：排序後雙指針 O(n log n)

若陣列較大，可先將兩陣列排序，再用雙指針單次遍歷計數：

sort(num); sort(cou);
int i = 0, j = 0, count = 0;
while(i < 5 && j < 5) {
    if(num[j] > cou[i]) { count += 5 - j; i++; }
    else j++;
}

時間從 O(n²) 降為 O(n log n)。

應用場景

• 統計學：Mann-Whitney U 檢定的核心計算。
• 遊戲：計算角色屬性相剋勝率。
• 推薦系統：用戶偏好向量比較。