Найти все дубликаты и отсутствующие значения в отсортированном массиве

Question

Предположим, что у вас есть отсортированный диапазон (от 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; 
} 

Я не тестировал детали валидации, поэтому может быть что-то не так с ними (особенно с дубликатами).

Я отправлю свое решение в качестве ответа.

Answer 1

Так как вы пометили его от языка, вот алгоритм я использовал бы.

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

Answer 2

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

Answer 3

мои любимый - 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 

Answer 4

Рубина:

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 

Answer 5

в питоне

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

Answer 6

Я думаю, что вы можете сделать это быстро на 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, что часто бывает. Бонус в том, что он линейно масштабируется по количеству элементов, что полезно :-)