等しいサイズの2つの配列がCで同じ値を持つかどうかをチェックする方法は？ （複雑性O（n））を

Question

編集：要素の値は0から99 に0から99までの範囲であっても可能ということですか？私は、次のコードを使用しようとしたが、それは明らかに間違っている：

#include <stdio.h> 

int scrambled(unsigned int a[], unsigned int b[], unsigned int len) { 
    if (len = 0) { 
     return 1; 
    } else { 
     int sumA, sumB, i; 
     for (i = 0; i < len; i++) { 
      sumA += a[i]; 
     } 
     for (i = 0; i < len; i++) { 
      sumB += b[i]; 
     } 
     if (sumA == sumB) { 
      return 1; 
     } else { 
      return 0; 
     } 
    } 
} 

私は同じ値の合計値を持つ2つの配列が同じ値を持っているでしょうが、これはそうではないと仮定しました。 {2,2}と{3,1}の合計は同じですが、同じ値ではありません。

は、別の言葉では、1つのアレイは線形複雑時間を持つ別の順列である、場合、私がチェックすることができる方法はありますか？

Answer 1

はい、C++でハッシュを使用する：

#include <iostream> 
#include <unordered_set> 

bool isEqual(int a1[], int a2[], int len) { 
    using namespace std; 
    unordered_set<int> s1(a1, a1 + len); //O(n) 
    unordered_set<int> s2(a2, a2 + len); // O(n) 
    return s1 == s2; // O(n) 
} 

int main() { 
    using namespace std; 
    int a1[5] = {5,2,3,4,1}; 
    int a2[5] = {1,3,2,5,4}; 
    std::cout << isEqual(a1, a2, sizeof(a1)/sizeof(int)) << std::endl; 

    int a3[5] = {0,2,3,4,5}; 
    int a4[5] = {1,6,2,5,4}; 
    std::cout << isEqual(a3,a4, sizeof(a3)/sizeof(int)) << std::endl; 
    return 0; 
} 

データに同じ値が存在する場合は、unordered_setを0123に交換します。また

： http://en.cppreference.com/w/cpp/container/unordered_set/operator_cmp

Nに

複雑比例は、VALUE_TYPEにオペレータ==の呼び出しkey_eqによって返された述語に を呼び出し、平均で、hash_functionによって 返さハッシャの呼び出しケースでは、最悪の場合N2に比例します。 ケースNはコンテナのサイズです。

より速い計画： は、あなたのデータによるとカスタムハッシュテーブルを実装します。たとえば、あなたのデータセットの範囲は何ですか？ 1つの配列にいくつの数値がありますか？

Answer 2

私は英語を話せず、私は専門家ではありません。

私はこの問題を理解しました。

私はこの問題は、あなたが、「SUMB」変数

須磨とSUMBが

は、私はあなたが考えるゴミ値を持つ「須磨」をリセットしないと思いその

int sumA = 0, sumB = 0, i; 

Answer 3

配列の要素の値が十分に小さい場合は、配列の最大値に等しい0の配列arrを保持できます。そして、1つのアレイのA次の要素を反復処理することができますし、1としてarr内の対応する要素をマーク。そして、他のアレイBのために、同じことを行うとBにないAのいずれかの要素があるかどうかを確認します。あなたは配列を変更することができる場合

#include <stdio.h> 
#define MAX 10000 
int arr[10000]; 
int scrambled(unsigned int a[], unsigned int b[], unsigned int len) 
{ 
    if (len=0) 
    { 
    return 1; 
    } 
    else 
    { 
     for (int i=0; i<len; i++) 
     { 
      arr[A[i]] = 1; 
     } 
     int same = 1; 
     for (int i=0; i<len; i++) 
     { 
      if(arr[B[i]] != 1) 
       same = 0; 
     } 
     if (same) 
     { 
      return 1; 
     } 
     else  
     { 
      return 0; 
     } 
    } 
} 

Answer 4

、あなたは基数ソートでそれらを並べ替え、簡単なforループとそれらを比較することができます。基数ソート時間Oの複雑さ（N *ログ（MAXN））maxNは、アレイ内の任意の数の最大値であるを有しています。 unsigned intのアレイのために、この最大値は、O（N）の定数、したがって時間の複雑さです。