2つの配列が同じ要素を持っているかどうかを効率的にチェックする方法（要素の順序は異なる場合も考慮）

ソートと比較

1. 2つの配列をソートします。
2. ソートされた配列を比較します。すべての要素が一致すれば、元の配列も同じ要素を持っていることになります。

この方法は単純ですが、ソートにO(n log n)の時間が必要となります。

ハッシュテーブルの使用

1. 1つの配列の要素をハッシュテーブルに格納します。
2. 2つ目の配列の各要素について、ハッシュテーブルに存在するかどうかをチェックします。すべての要素が存在すれば、元の配列も同じ要素を持っていることになります。

この方法は、ハッシュテーブルの検索時間がO(1)であるため、平均的な時間計算量はO(n)となります。

ビットマスクの使用

1. 各要素をビットマスクに変換します。
2. 2つのビットマスクを論理積します。
3. 論理積の結果が0であれば、2つの配列は同じ要素を持っていることになります。

この方法は、要素の数が少ない場合に効率的です。

以下のコードは、2つの配列が同じ要素を持っているかどうかをチェックする例です。

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

// ソート関数
void sort(int *array, int size) {
  // ...
}

// ハッシュテーブル
typedef struct node {
  int key;
  int value;
} node;

node *hash_table[100000];

void hash_init() {
  for (int i = 0; i < 100000; i++) {
    hash_table[i] = NULL;
  }
}

void hash_insert(int key, int value) {
  // ...
}

int hash_find(int key) {
  // ...
}

// ビットマスク
int bitmask(int x) {
  // ...
}

int main() {
  int n;
  scanf("%d", &n);

  int array1[n], array2[n];
  for (int i = 0; i < n; i++) {
    scanf("%d", &array1[i]);
  }
  for (int i = 0; i < n; i++) {
    scanf("%d", &array2[i]);
  }

  // ソートと比較
  sort(array1, n);
  sort(array2, n);
  bool same = true;
  for (int i = 0; i < n; i++) {
    if (array1[i] != array2[i]) {
      same = false;
      break;
    }
  }
  if (same) {
    printf("Yes\n");
  } else {
    printf("No\n");
  }

  // ハッシュテーブルの使用
  hash_init();
  for (int i = 0; i < n; i++) {
    hash_insert(array1[i], i);
  }
  same = true;
  for (int i = 0; i < n; i++) {
    if (hash_find(array2[i]) == -1) {
      same = false;
      break;
    }
  }
  if (same) {
    printf("Yes\n");
  } else {
    printf("No\n");
  }

  // ビットマスクの使用
  int mask1 = 0, mask2 = 0;
  for (int i = 0; i < n; i++) {
    mask1 |= bitmask(array1[i]);
    mask2 |= bitmask(array2[i]);
  }
  if (mask1 == mask2) {
    printf("Yes\n");
  } else {
    printf("No\n");
  }

  return 0;
}

どの方法を使うべきか

どの方法を使うべきかは、要素の数、要素の範囲、処理速度などの条件によって異なります。

• ハッシュテーブルの使用は、平均的な時間計算量がO(n)であるため、要素の数が多い場合に効率的です。

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

// ソート関数
void sort(int *array, int size) {
  // ...
}

// ハッシュテーブル
typedef struct node {
  int key;
  int value;
} node;

node *hash_table[100000];

void hash_init() {
  for (int i = 0; i < 100000; i++) {
    hash_table[i] = NULL;
  }
}

void hash_insert(int key, int value) {
  // ...
}

int hash_find(int key) {
  // ...
}

// ビットマスク
int bitmask(int x) {
  // ...
}

int main() {
  int n;
  scanf("%d", &n);

  int array1[n], array2[n];
  for (int i = 0; i < n; i++) {
    scanf("%d", &array1[i]);
  }
  for (int i = 0; i < n; i++) {
    scanf("%d", &array2[i]);
  }

  // ソートと比較
  sort(array1, n);
  sort(array2, n);
  bool same = true;
  for (int i = 0; i < n; i++) {
    if (array1[i] != array2[i]) {
      same = false;
      break;
    }
  }
  if (same) {
    printf("Yes\n");
  } else {
    printf("No\n");
  }

  // ハッシュテーブルの使用
  hash_init();
  for (int i = 0; i < n; i++) {
    hash_insert(array1[i], i);
  }
  same = true;
  for (int i = 0; i < n; i++) {
    if (hash_find(array2[i]) == -1) {
      same = false;
      break;
    }
  }
  if (same) {
    printf("Yes\n");
  } else {
    printf("No\n");
  }

  // ビットマスクの使用
  int mask1 = 0, mask2 = 0;
  for (int i = 0; i < n; i++) {
    mask1 |= bitmask(array1[i]);
    mask2 |= bitmask(array2[i]);
  }
  if (mask1 == mask2) {
    printf("Yes\n");
  } else {
    printf("No\n");
  }

  return 0;
}

説明

• ハッシュテーブルの使用: 1つの配列の要素をハッシュテーブルに格納します。2つ目の配列の各要素について、ハッシュテーブルに存在するかどうかをチェックします。すべての要素が存在すれば、元の配列も同じ要素を持っていることになります。
• ビットマスクの使用: 各要素をビットマスクに変換します。2つのビットマスクを論理積します。論理積の結果が0であれば、2つの配列は同じ要素を持っていることになります。

各方法の詳細

ソートと比較

sort(array1, n);
sort(array2, n);
bool same = true;
for (int i = 0; i < n; i++) {
  if (array1[i] != array2[i]) {
    same = false;
    break;
  }
}

1. sort()関数を使って2つの配列をソートします。
2. ソートされた配列を比較します。すべての要素が一致すれば、same変数がtrueのままになります。
3. 1つでも要素が一致しない場合は、same変数がfalseになり、ループが終了します。

hash_init();
for (int i = 0; i < n; i++) {
  hash_insert(array1

2つの配列を順番を入れ替えても同じ要素であれば、同じ要素を持っていることになります。

集合演算の使用

2つの配列を集合と見なし、集合演算を使用して同じ要素を持っているかどうかをチェックします。

ライブラリの使用

C言語には、配列の比較を行うライブラリが用意されています。

これらのライブラリを使用すると、簡単に配列の比較を行うことができます。

bool is_same_permutation(int *array1, int *array2, int n) {
  // ...
}

int main() {
  int n;
  scanf("%d", &n);

  int array1[n], array2[n];
  for (int i = 0; i < n; i++) {
    scanf("%d", &array1[i]);
  }
  for (int i = 0; i < n; i++) {
    scanf("%d", &array2[i]);
  }

  if (is_same_permutation(array1, array2, n)) {
    printf("Yes\n");
  } else {
    printf("No\n");
  }

  return 0;
}

このコードは、is_same_permutation()関数を使用して2つの配列が同じ要素を持っているかどうかをチェックします。