3

これは 1 億個の整数を含むビッグデータですが、その中には他の同じ整数に対して 1 つの異なる値があります。 1..しかし、次のコードに何が起こったのかわかりません。

int main() {

    vector <int> data;
    cout << "Enter same numbers " << " and a different one( negative to be end) :" << endl;
    int value;
    while (cin >> value && value > 0) {
        data.push_back(value);
    }
    int unique_value;
    int size = data.size();
    if (data[0] != data[size - 1]) {
        if (data[0] != data[2]) {
            unique_value = data[0];
        } else {
            unique_value = data[size - 1];
        }
        cout << "found the unique number: " << unique_value << endl;
        exit(0);
    }
    int low = 1;
    int high = size - 2;
    while (high > low) {
        if (data[high] != data[low]) {
            //其中必有一个是不同的，只要和data[0]就能得到结果
            if (data[high] != data[0]) {
                unique_value = data[high];
            } else {
                unique_value = data[low];
            }
            break;
        }
    }
    if (high == low) {
        unique_value = data[high];
    }
    cout << "found the unique number: " << unique_value << endl;
    return 0;
}
4

4 に答える 4

9

最初の3つの要素を並べ替え、真ん中の要素を取得します。それはあなたの一意でない番号です。リストを調べて、それとは異なる番号を探します。

int data[] = {7,7,7,7,7,7,42,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7};
size_t N = sizeof(data)/sizeof(data[0]);
sort(data, data+3);
int non_unique = data[1];
for (int i = 0 ; i != N ; i++) {
    if (data[i] != non_unique) {
        cout << data[i] << endl;
        break;
    }
}

ideoneへのリンク。

于 2012-09-07T01:23:29.747 に答える
0

まず、コードのどこが悪いのかということです。while2つの変数によって制御されhigh、ループlow内で更新されないループがあるため、永久に回転します。

アルゴリズムに関しては、異なる番号を見つけるために番号を保存する必要はありません。むしろ、最初の2つの番号を読み取ることができます。異なる場合は、3番目の番号を読み取って答えが得られます。それらが同じである場合は、それらの1つを保持し、異なるものが見つかるまで番号を読み続けます。

// omitting checks for i/o errors, empty list and single number list:
// and assuming that there is one that is different
int main() {
   int first;
   int current;
   std::cin >> first >> current; 
   if (first != current) {
      int third;
      std::cin >> third;
      if (first==third) {
         std::cout << current << "\n";
      } else {
         std::cout << first << "\n";
      }
      return 0;
   }
   while (std::cin >> current && current == first) ;
   std::cout << current << "\n";
}

そのスケッチに加えて、入力エラーと、その一般的なアルゴリズムで管理されていないコーナーケース（空のリスト、1つの要素リスト、2つの要素リスト）を処理する必要があります。

于 2012-09-07T02:32:19.097 に答える
0

入力できる数値が2 つしかないと仮定すると(「他の整数に対する 1 つの異なる値」)、それらすべてを保存する必要はありません。その場合は、 のように入力します1,1,1,1,1,1,1,42,1,1,1,1。

その場合は、（疑似コード）のようなものを使用できます。

firstNum = 0; firstCount = 0
secondNum = 0; secondCount = 0
while true:
    num = getNumber()
    if num < 0:
        break while

    if firstCount == 0:                  # first unique number
        firstNum = num
        firstCount = 1
        next while

    if num == firstNum:                  # copy of first
        firstCount++
        next while

    if secondCount == 0:                 # second unique number
        secondNum = num
        secondCount = 1
        next while

    if num <> secondNum:                 # third unique number (disallowed)
        print "Only two numbers allowed"
        stop run

    secondNum++                          # was the second unique number

if secondNum == 0:                       # there was < 2 unique numbers
    print "Not enough different numbers"
    stop run

if firstCount > 1 and secondCount > 1:   # there were no unique numbers
    print "No one unique number"
    stop run

if firstCount == 1:                      # Choose number with count of 1
    print "Unique number is " firstNum
else
    print "Unique number is " secondNum

代わりに、多数の異なる番号が存在する可能性がある場合は、すべての番号を他のすべての番号と照合するソリューションが必要になります。

これはさまざまな方法で行うことができます (他にもあるかもしれません。これらは頭に浮かんだ最初のいくつかです)。

  • 遅い O(n^2) は、すべての数値を他のすべての (後続の) 数値に対してチェックします。
  • その後、ソートがわずかに高速になり（おそらくO（log N））、ソートされたリストを調べて、隣接する番号を互いにチェックします。
  • 入力範囲が限られている場合は、考えられる数値ごとにカウント配列を使用して、最終的にカウントが 1 になるものを探すことができます (他のものも同じようにならないようにします)。

ご質問文からは、そうではないと思いますが、その点についても触れておいたほうがよいと思います。

于 2012-09-07T01:27:13.397 に答える
0

誰もがそれを行う方法を教えてくれましたが、あなたの質問には答えていません: あなたのコードの何が問題なのですか?

問題は、ループ内でhighandの値を決して変更しないため、コードが終了しないことです。low配列の両端から作業し、2 つの値を配列の最初の要素と比較しています。これにより、最初の if ブロックが冗長になり、実際には少し奇妙になります。これは、3 番目の配列要素を (境界チェックなしで) 調べるためです。

だから...この部分を取り出してください：

//if (data[0] != data[size - 1]) {
//    if (data[0] != data[2]) {
//        unique_value = data[0];
//    } else {
//        unique_value = data[size - 1];
//    }
//    cout << "found the unique number: " << unique_value << endl;
//    exit(0);
//}

そしてループを修正します：

int low = 1;
int high = size - 1;
while (high >= low) {
    if( data[high] != data[0] )
    {
        if (data[low] == data[high]) {
            unique_value = data[high];
        } else {
            unique_value = data[0];
        }
        break;
    }
    else if( data[low] != data[0] )
    {
        unique_value = data[low];
        break;
    }
    low++;
    high--;
}

// Take out the part that compares high==low.  It was wrong, and has been made
// redundant by looping while high >= low (instead of high > low).

それはうまくいくはずです。しかし、それは奇妙です。

ここで、この方法で配列を検索することは、キャッシュの局所性のために悪い考えであることに注意してください。最適化の理由から、検索をメモリの同じ部分に制限したい場合、このアルゴリズムでは、配列内の 3 つの隣接する値を調べてはならない理由はありません。

実際、最初の 3 つだけを調べる必要があります。その後、一意でない値のいずれか、またはその両方を決定します。最初の 3 つの要素がすべて同じである場合は、別の値が見つかるまで、配列の残りの部分を線形検索するだけです...値を配列に読み込む必要さえないことは既に指摘されています。 . これはオンザフライで実行できます。

size_t size = data.size();

if( size < 3 ) {
    cerr << "Not enough data\n";
    exit(0);
}

int unique_val = 0;

if( data[1] == data[0] && data[2] == data[0] ) {
    int common_val = data[0];
    for( int i = 3; i < size; i ++ ) {
        if( data[i] == common_val ) continue;
        unique_val = data[i];
        break;
    } 
}
else if( data[1] != data[0] ) {
    if( data[2] == data[1] )
       unique_val = data[0];
    else
       unique_val = data[1];
}
else {
    unique_val = data[2];
}

if( unique_val == 0 ) {
    cout << "No unique value found\n";
} else {
    cout << "Unique value is " << unique_val << "\n";
}
于 2012-09-07T02:39:18.513 に答える