如何在一串数字中找到一个不同的值

Question

这是一个大数据，其中包含1亿个整数，但其中包含一个与其他相同整数不同的值，例如：1,1,1,1 ，1,1,1,42,1,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; 
} 

Answer 1

对前三个元素进行排序，取其中一个。这是你的非唯一编号。浏览清单，并寻找一个数字，从它不同：

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.

Answer 2

假设有你被允许输入（“一个不同的值只针对可能的数字其他整数“），则不需要全部存储它们。在这种情况下，您将输入如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的计数（确保没有其他人做的一样好）。

根据您的问题文本，我不认为是这样的话，但我想结束了一个我最好盖那

Answer 3

第一件事是你的代码有什么问题你有一个while循环由两个变量控制high和low，它们不在循环内更新，因此它将永远旋转。

至于算法，你不需要存储数字来找到不同的数字，而是你可以阅读前两个数字，如果它们不同，读取第三个数字并且你有答案。如果它们是相同的，让他们中的一个，并继续阅读数字，直到你找到一个不同的是：

// 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个元素列表）不是由该通用算法管理的。

Answer 4

大家都告诉过你他们如何会这样做，但还没有回答你的问题：你的代码有什么问题？

问题是您的代码永不终止，因为您永远不会更改循环中的high和low值。您正在从数组的两端开始工作，并将两个值与数组中的第一个元素进行比较。现在，这使得你的第一个if块是多余的，实际上有点奇怪，因为它检查了第三个数组元素（没有任何边界检查）。

所以......就拿这部分指出：

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

这应该工作。但这很奇怪。

现在，请注意，以这种方式搜索您的数组是一个坏主意，因为缓存局部性。由于优化的原因，你想限制你的搜索到同一部分内存，对于这种算法，没有理由不检查数组中的三个相邻值。

实际上，您只需要检查前三个，之后您将确定非唯一值或两者。如果前三个元素完全相同，则只需对数组的其余部分执行线性搜索，直到找到不同的值为止......已经指出，您甚至不必将值读入数组。你可以在飞行中做到这一点。

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