查找排序的阵列中的所有重复和缺失值 [英] Find all duplicates and missing values in a sorted array

问题描述

假设值，你有一个排序的范围（x到y）在数组中。

Suppose you have a sorted range (x to y) of values in an array.

x = 3;
y = 11;

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

但它是可能的一些值是重复的，有些是失踪，所以你可能有：

But it is possible that some values are duplicated and some are missing, so you might have:

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

是什么在你的语言找到所有重复和缺失值，所以最好的方式，你可以获得：

What's the best way in your language to find all duplicates and missing values so you get:

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

下面是一些C ++ code，让你开始：

Here's some C++ code to get you started:

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

我没有测试验证的部分很多，所以有可能是坏了他们（尤其是重复的一个）。

I didn't test the validation parts much, so there may be be something wrong with them (especially with the duplicates one).

我会后我自己的解决方案作为一个答案。

I will post my own solution as an answer.

推荐答案

既然你已经将其标记语言无关，这里的算法，我会使用。

Since you've marked it language-agnostic, here's the algorithm I'd use.

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

这篇关于查找排序的阵列中的所有重复和缺失值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！