如何在一串數字中找到一個不同的值

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