counting duplicates in c++

2019-02-25 02:32发布

Let's say I have an array of ints {100, 80, 90, 100, 80, 60}

so I want to count those duplicates and save those counter for later. because each duplicate number should be divided by counter

like 100 is duplicated 2 times so they should be 50 each.

to find duplicates, I used sort.

std::sort(array, array + number);
for(int i = 0; i < number; i++) {
  if(array[i] == array[i+1])
    counter++;
}

and I've tried to make counter array to save them on each num of array. but it didn't work. please give me some better idea.

4条回答
对你真心纯属浪费
2楼-- · 2019-02-25 03:03

If you want to change the array numbers directly, you may proceed like this:

for (int i = 0, counter = 1; i < number; i++) {
    if (array[i] == array[i + 1])
        counter++;
    else { //when finished counting duplicates
        for (int j = counter; j > 0; j--) //adjustment for subscripts
            array[i - j + 1] /= counter; //change the values stored in array
        counter = 1;//reinitialize array to 1
    }
}

Your sorted values stored in the array will come out already divided once by their corresponding counters.

查看更多
一纸荒年 Trace。
3楼-- · 2019-02-25 03:09

Use a std::map<int,int> or std::unordered_map for counting the occurences.

Then iterate over the map and replace each value by the key divided by the original value (counter).

Finally go through the original array and replace each number by its mapped value.

If you use a std::unordered_map the algorithm is O(n). Your original one is O(n log n) because sorting is involved.

查看更多
冷血范
4楼-- · 2019-02-25 03:15

Here is algo to replace elements in place if you are allowed to modify sequence:

const auto begin = std::begin( data );
const auto end = std::end( data );
std::sort( begin, end );
for( auto it = begin; it != end; ) {
    auto next = std::upper_bound( std::next( it ), end, *it );
    auto newval = *it / std::distance( it, next );
    std::fill( it, next, newval );
    it = next;
}

demo on ideone

PS modified to make it compile with array as well.

查看更多
Explosion°爆炸
5楼-- · 2019-02-25 03:26

Approach 1

The easiest way, is not to sort your array, and increment elements of a map:

unordered_map<int, size_t> count;  // holds count of each encountered number 
for (int i=0; i<number; i++)        
    count[array[i]]++;             // magic ! 

You can then process the content of the map:

for (auto &e:count)                // display the result 
    cout << e.first <<" : "<<e.second<< "-> "<<e.first/e.second<<endl; 

If needed, filter out the non duplicates by rerasing them from the map or ignoring it during the processing.

Approach 2

If you're not allowed to use maps, then you have to elaborate your counting loop, in order to restart counting for each new number, and being able to process consecutive dups also if more than two:

...
for(int i = 0; i < number; i+=counter) {
    for (counter=1; i+counter<number && array[i+counter]==array[i]; ) 
        counter++;       // count consecutives dups
    if (counter>1) {     // if more than one, process the dups.  
        cout << "dup: " << array[i] << " "<<counter<<endl;   
    }
}

If you need to store the pairs to process them in asecond step, you need to store a pair (preferably in a vector, but if needed in an array):

pair<int, size_t> result[number];  // a vector would be preferable
int nres=0; 
... 
    if (counter>1) {     // if more than one, process the dups.  
        // cout << "dup: " << array[i] << " "<<counter<<endl; 
        result[nres++] = make_pair(array[i], counter);  
    }
...

Online demo for both approaches

查看更多
登录 后发表回答