CODEWITHSUNDEEP
c++arrays
user9432978
user9432978

Reputation:

Find equals value into an array in c++

There is a faster way to find equals value into an array instead of comparing all elements one by one with all the array's elements ?

for(int i = 0; i < arrayLenght; i ++)
{
    for(int k = i; k < arrayLenght; i ++)
    {
        if(array[i] == array[k])
        {
            sprintf(message,"There is a duplicate of %s",array[i]);
            ShowMessage(message);
            break;
        }
    }
}

Upvotes: 1

Views: 1452

Answers (4)

Luis Colorado
Luis Colorado

Reputation: 12668

In case you have a large amount of data, you can first sort the array (quick sort gives you a first pass in O(n*log(n))) and then do a second pass by comparing each value with the next (as they might be all together) to find duplicates (this is a sequential pass in O(n)) so, sorting in a first pass and searching the sorted array for duplicates gives you O(n*log(n) + n), or finally O(n*log(n)).

EDIT

An alternative has been suggested in the comments, of using a std::set to check for already processed data. The algorithm just goes element by element, checking if the element has been seen before. This can lead to a O(n) algorithm, but only if you take care of using a hash set. In case you use a sorted set, then you incur in an O(log(n)) for each set search and finish in the same O(n*log(n)). But because the proposal can be solved with a hash set (you have to be careful in selecting an std::unsorted_set, so you don't get the extra access time per search) you get a final O(n). Of course, you have to account for possible automatic hash table grow or a huge waste of memory used in the hash table.

Thanks to @freakish, who pointed the set solution in the comments to the question.

Upvotes: 0

Killzone Kid
Killzone Kid

Reputation: 6240

You could use std::multiset and then count duplicates afterwards like this:

#include <iostream>
#include <set>

int main()
{
    const int arrayLenght = 14;
    int array[arrayLenght] = { 0,2,1,3,1,4,5,5,5,2,2,3,5,5 };

    std::multiset<int> ms(array, array + arrayLenght);

    for (auto it = ms.begin(), end = ms.end(); it != end; it = ms.equal_range(*it).second)
    {
        int cnt = 0;
        if ((cnt = ms.count(*it)) > 1)
            std::cout << "There are " << cnt << " of " << *it << std::endl;
    }
}

https://ideone.com/6ktW89

There are 2 of 1
There are 3 of 2
There are 2 of 3
There are 5 of 5

Upvotes: 2

choxsword
choxsword

Reputation: 3359

If your value_type of this array could be sorted by operator <(a strict weak order) it's a good choice to do as YSC answered.

If not,maybe you can try to define a hash function to hash the objects to different values.Then you can do this in O(n) time complexity,like: 

struct ValueHash
{
    size_t operator()(const Value& rhs) const{
        //do_something
    }
};
struct ValueCmp
{
    bool operator()(const Value& lhs, const Value& rhs) const{
          //do_something
    }
};
unordered_set<Value,ValueHash,ValueCmp> myset;
for(int i = 0; i < arrayLenght; i ++)
{
    if(myset.find(array[i])==myset.end())
          myset.insert(array[i]);
    else
         dosomething();
}

Upvotes: 1

YSC
YSC

Reputation: 40080

Since sorting your container is a possible solution, std::unique is the simplest solution to your problem:

std::vector<int> v {0,1,0,1,2,0,1,2,3};
std::sort(begin(v), end(v));
v.erase(std::unique(begin(v), end(v)), end(v));

First, the vector is sorted. You can use anything, std::sort is just the simplest. After that, std::unique shifts the duplicates to the end of the container and returns an iterator to the first duplicate. This is then eaten by erase and effectively removes those from the vector.

Upvotes: 4

Related Questions