查找排序後的數組中的所有重複項和缺失值

假設您有一個數組值範圍（x到y）。查找排序後的數組中的所有重複項和缺失值

x = 3; 
y = 11; 

array == 3, 4, 5, 6, 7, 8, 9, 10, 11

但它可能是一些價值被複制和一些缺失，所以你可能有：

array == 4, 5, 5, 5, 7, 8, 9, 10, 10

是什麼在你的語言找到所有重複和缺失值，所以你得到的最好方式：

resultMissingValuesArray == 3, 6, 11 
resultDuplicatesArray == 5, 5, 10

這裏的一些C++代碼，讓你開始：

#include <vector> 
#include <iostream> 
#include <algorithm> 

using namespace std; 

const int kLastNumber = 50000; // last number expected in array 
const int kFirstNumber = 3; // first number expected in array 

int main() 
{ 
    vector<int> myVector; 

    // fill up vector, skip values at the beginning and end to check edge cases 
    for(int x = kFirstNumber + 5; x < kLastNumber - 5; x++) 
    { 
     if(x % 12 != 0 && x % 13 != 0 && x % 17 != 0) 
      myVector.push_back(x); // skip some values 

     else if(x % 9 == 0) 
     { 
      myVector.push_back(x); // add duplicates 
      myVector.push_back(x); 
     } 

     else if(x % 16 == 0) 
     { 
      myVector.push_back(x); // add multiple duplicates 
      myVector.push_back(x); 
      myVector.push_back(x); 
      myVector.push_back(x); 
     } 
    } 

    // put the results in here 
    vector<int> missingValues; 
    vector<int> duplicates; 

    // YOUR CODE GOES HERE   

    // validate missingValues for false positives 
    for(int x = 0; x < (int) missingValues.size(); ++x) 
    { 
     if(binary_search(myVector.begin(), myVector.end(), missingValues.at(x))) 
      cout << "Oh noes! You missed an unmissed value. Something went horribly, horribly wrong."; 
    } 

    // validate duplicates (I think... errr) 
    vector<int>::iterator vecItr = myVector.begin(); 
    vector<int>::iterator dupItr = duplicates.begin(); 

    while(dupItr < duplicates.end()) 
    { 
     vecItr = adjacent_find(vecItr, myVector.end());  

     if(*vecItr != *dupItr) 
      cout << "Oh noes! Something went horribly, horribly wrong."; 

     // oh god 
     while(++dupItr != duplicates.end() && *(--dupItr) == *(++dupItr) && *vecItr == *(++vecItr));    

     ++vecItr; 
    } 

    return 0; 
}

我沒有對驗證部分進行太多的測試，所以可能會出現問題（特別是對於重複的問題）。

我會發布我自己的解決方案作爲答案。

來源

2009-02-26 drby

既然你已經將其標記語言無關，這裏的算法，我會使用。

# Get numbers and sort them in ascending order. 

input x,y; 
input number[1..n]; 
sort number[1..n]; 

# Set dups and missing to empty sets. 

dups = []; 
missing = []; 

# Get edge cases. 

if number[1] > x: 
    foreach i x .. number[1] - 1: 
     missing.add(i) 
if number[n] < y: 
    foreach i number[n] + 1 .. y: 
     missing.add(i) 

# Process all numbers starting at second one. 

foreach i 2 .. n: 
    # If number same as last and not already in dups set, add it. 

    if number[i] == number[i-1] and not dups.contains(number[i]): 
     if number[i] >= x and number[i] <= y: 
      dups.add(number[i]) 

    # If number not last number plus one, add all between the two 
    # to missing set. 

    if number[i] != number[i-1] + 1: 
     foreach j number[i-1] + 1 .. number[i] - 1: 
      if j >= x and j <= y: 
       missing.add(j)

來源

2009-02-26 11:24:25 paxdiablo

感嘆。這太好了。起初，我嘗試將它作爲for循環來使用，但我不知何故陷入了錯誤的軌道，並以可憎的方式結束。感謝這個答案。（最後一行應該是missing.add（j），雖然，我認爲） – drby 2009-02-26 12:14:11

if(myVector.front() > kFirstNumber) 
    for(int x = kFirstNumber; x < myVector.at(0); ++x) 
     if(x >= kFirstNumber && x <= kLastNumber) 
      missingValues.push_back(x); 

for(int x = 1; x < (int) myVector.size(); ++x) 
{ 
    if(myVector.at(x) == myVector.at(x - 1)) 
     if(x >= kFirstNumber && x <= kLastNumber) 
      duplicates.push_back(myVector.at(x)); 

    if(myVector.at(x) != myVector.at(x - 1) + 1) 
     for(int y = myVector.at(x - 1) + 1; y <= myVector[x] - 1; y++) 
      if(y >= kFirstNumber && y <= kLastNumber) 
       missingValues.push_back(y); 
} 

if(myVector.back() < kLastNumber) 
    for(int x = myVector.back() + 1; x <= kLastNumber; ++x) 
     if(x >= kFirstNumber && x <= kLastNumber) 
      missingValues.push_back(x);

（我的解決方案是相當難看，所以我用C++實現大同的算法取代它。）

來源

2009-02-26 11:22:36 drby

最後在最後添加缺失值的循環可簡化爲「while（itr <= kLastNumbers）{missingValues.push_back（itr ++ ）;}「。您不需要missingAtEnd或if語句。 – 2009-02-26 11:30:45

我的最愛 - Python的，很簡單：

x = 3 
y = 11 
array = [ 3, 4, 5, 6, 7, 8, 9, 10, 11 ] 
test = [ 4, 5, 5, 5, 7, 8, 9, 10, 10 ] 

resultMissingValuesArray = set(range(x,y+1)).difference(test)   
resultDuplicatesArray = reduce(lambda i,j: i+j, [[n]*(test.count(n)-1) for n in set(test) if test.count(n)>1], [])

副本可以通過這條線可以更容易地發現：

resultDuplicatesArray = [n for n in set(test) if test.count(n)>1] 
# [5, 10] - just numbers, that have duplicates 
# you can use test.count(5) for number of duplicates

來源

2009-02-26 11:47:57 Jiri

紅寶石：

x = 3 
y = 11 
array = [ 4, 5, 5, 5, 7, 8, 9, 10, 10 ] 

resultMissingValuesArray = (x..y).to_a - array 
resultDuplicatesArray = array.delete_if { |e| array.index(e) == array.rindex(e) }.uniq

來源

2009-02-26 12:07:06

在python

consecutive=zip(l[0:-1],l[1:]) 
duplicate=[ a for (a,b) in consecutive if a==b] 
missing=reduce(lambda u,v:u+v, [range(a+1,b) for (a,b) in consecutive])

來源

2009-02-26 13:43:09 fulmicoton

我認爲你可以在C++中快速執行此操作，方法是設置第二個數組作爲檢查，以查看哪些元素已找到，然後在每次找到元素時將其元素遞增一。所以：

int array = [3,4,5,6,7,8,9,10,11]; 
unsigned array_size = 9; 
int test = [4,5,5,5,7,8,9,10,10]; 

// Find the maximum element in array 
// This might not be necessary if it's given somewhere 
unsigned max = 0; 
unsigned min = -1; 
for(unsigned i = 0; i < array_size; i++){ 
    if(array[i] > max) max = array[i]; 
    if(array[i] < min) min = array[i]; 
} 

// Go make a counts vector to store how many examples of each value there are 
vector<unsigned> counts(max+1, 0); 
for(unsigned i = 0; i < array_size; i++) 
    counts[test[i]]++; 

// Gather the unique elements, duplicates and missing elements 
vector<unsigned> unique; 
vector<unsigned> duplicates; 
vector<unsigned> missing; 
for(unsigned i = min; i < max + 1; i++){ 
    switch(counts[i]){ 
     case 0 : missing.push_back(i); break; 
     case 1 : unique.push_back(i);  break; 
     default: duplicates.push_back(i); 
    } 
}

這隻適用於如果你的數組中大於0的數字，通常是這種情況。獎勵是它在元素數量上線性縮放，這很有用:-)

來源

2009-08-03 14:47:50

查找排序後的數組中的所有重複項和缺失值

回答

相關問題