C言語で配列から重複する数字を探すにはどうすればいいですか

2年 ago
蓮, 翼
1 minute

配列内の重複した数値を見つける方法は2つあります。

１：ハッシュテーブルを利用

  1. 各数字の出現回数を記録するためのハッシュ表を作成します。
  2. 配列を走査して、配列の各数値をキーとしてハッシュテーブルに入れ、対応する値に 1 を加算する。
  3. ハッシュテーブルを走査して、値が1より大きいキーを見つけ、重複する数字とします。

このコードの例は以下の通りです

#include <stdio.h>

void findDuplicates(int arr[], int size) {
    // 哈希表
    int hashTable[1000] = {0};
    
    // 遍历数组，将数字放入哈希表
    for (int i = 0; i < size; i++) {
        hashTable[arr[i]] += 1;
    }
    
    // 遍历哈希表，找出重复的数字
    for (int i = 0; i < 1000; i++) {
        if (hashTable[i] > 1) {
            printf("%d ", i);
        }
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 4, 5, 6, 6, 7};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    printf("重复的数字为：");
    findDuplicates(arr, size);
    
    return 0;
}

2番目の方法：交換法を用いる

  1. 各要素をインデックスの位置に格納するよう配列を反復処理する。
  2. 現在のインデックスの位置にすでに同じ数字がある場合、重複する数字は発見されました。

コードのサンプルが以下に示されています。

#include <stdio.h>
#include <stdbool.h>

void findDuplicates(int arr[], int size) {
    printf("重复的数字为：");
    
    for (int i = 0; i < size; i++) {
        while (arr[i] != i) {
            if (arr[i] == arr[arr[i]]) {
                printf("%d ", arr[i]);
                break;
            }
            
            int temp = arr[arr[i]];
            arr[arr[i]] = arr[i];
            arr[i] = temp;
        }
    }
}

int main() {
    int arr[] = {1, 2, 3, 4, 4, 5, 6, 6, 7};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    findDuplicates(arr, size);
    
    return 0;
}

どちらの手法も重複値を配列から見つけることができますが、どちらを選択するかは具体的なニーズとデータの規模に依存します。

bannerAds