how to find one single different value in a bunch of numbers

Question

This is a big data, which contains 100 million integers, but among which it has one different value against the other same integers,eg:1,1,1,1,1,1,1,42,1,1,1,1.. However, I don't know what happened to my following code.

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;
}

Answer 1

Everyone has told you how they would do it, but haven't answered your question: what is wrong with your code?

The problem is your code never terminates because you never change your high and low values in the loop. You are working from both ends of the array and comparing two values to the first element in the array. Now, this makes your first if-block redundant and in fact a bit odd, because it examines the third array element (without any bounds-checking).

So... Take this part out:

//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);
//}

And fix the loop:

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).

That should work. But it's weird.

Now, note that searching your array in this way is a bad idea because of cache locality. You want to constrain your searches to the same part of memory for optimization reasons, and for this algorithm there is no reason why you shouldn't just examine three adjacent values in the array.

In fact, you only need to examine the first three, after which time you will have determined either the non-unique value, or both. If the first three elements are all the same, you simply do a linear search through the rest of the array until you find a different value... It's already been pointed out that you don't even have to read the values into an array. You can do this on the fly.

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";
}

Answer 2

The first thing is what is wrong with your code. You have a while loop controlled by two variables high and low that are not updated inside the loop, and thus it will spin forever.

As to the algorithm, you don't need to store the numbers to find the one that is different, rather you can read the first two numbers, if they differ read a third number and you have the answer. If they are the same, keep one of them and continue reading numbers until you find one that is different:

// 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";
}

On top of that sketch you will need to handle input errors, as well as corner cases (empty list, 1 element list, 2 element list) that are not managed by that generic algorithm.

Answer 3

Assuming that there are only two possible numbers you're allowed to input ("one different value against the other integers"), you don't need to store them all. In that case, you'll have input like 1,1,1,1,1,1,1,42,1,1,1,1.

If that is the case, you can use something like (pseudo-code):

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

---

If instead, there can be a host of different numbers, you'll need a solution that checks every number against every other number.

This can be done in a variety of ways (there may be others, these are just the first few that sprang to mind):

• slow O(n^2) checking every number against every other (subsequent) number.
• slightly faster sorting then (likely O(log N), then going through the sorted list checking adjacent numbers against each other.
• if the input range is limited, you can use a count array for each possible number and look for the one that ends up with a count of 1 (ensuring no others do as well).

Based on your question text, I don't think that's the case, but I thought I'd better cover that aspect as well.

Answer 4

Sort the first three elements, and take the middle one. It's your non-unique number. Go through the list, and look for a number that is different from it:

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;
    }
}

Link to ideone.