Как найти количество дубликатов в массиве?

Question

У меня есть заданный массив, и мне нужно определить, как найти количество дубликатов в нем. Я должен сделать это с помощью вложенных циклов и не использовать векторы. Я пробовал это до сих пор, и я получаю 3, но ответ должен быть 2, поскольку повторяются только цифры 4 и 7. Я понимаю, почему я получаю 3, так как он проверяет 4 раза два, но я не могу понять, как настроить его, чтобы он никогда не проверял еще 4, как только он нашел совпадение.

#include <iostream> 
using namespace std; 

int main() { 
    const int num_elements = 12; 
    int numbers[num_elements] = { 2, 6, 7, 4, 5, 4, 1, 8, 9, 0, 7, 4 }; 

    unsigned int numduplicates = 0;  
    for(int i = 0; i < num_elements; ++i){ 
     int oneCounterMax = 0; 
     for(int j = i + 1; j < num_elements; ++j) { 
      if((numbers[i] == numbers[j]) && (oneCounterMax < 1)) { 
       ++numduplicates; 
       ++oneCounterMax; 
      }  

     } 
    }  
    cout << numduplicates << endl; 
} 

Answer 1

Лучшим способом было бы использовать std::vector и std::map, как уже упоминалось другими. Но так как вы можете использовать только вложенные циклы и массивы здесь пример, который работает:

const int num_elements = 12; 
int numbers[num_elements] = { 2, 6, 7, 4, 5, 4, 1, 8, 9, 0, 7, 4 }; 
int counter = 0; 

for (int i = 0; i < num_elements; i++) { 
    for (int j = i + 1; j < num_elements; j++) { 
     if (numbers[j] == numbers[i]) { 
      counter++; 
      for (int k = 0; k < i; k++) { 
       if (numbers[k] == numbers[j]) { 
        counter--; 
        break; 
       } 
      } 
      break; 
     } 
    } 
} 

cout << counter << endl; 

Он будет печатать 2 и не 3. Просто, когда мы находим дубликат, мы возвращаемся и проверяем, уже ли мы встретили это число.

Answer 2

Вы можете использовать карту, например, где key - номер [i], а значение - числовое число [i].

std::map<int,int> m; 
std::map<int,int>::iterator it; 
for(int i = 0; i < num_elements; ++i) { 
    const int key = numbers[i]; 
    int value = 0; 
    it = m.find(key) 
    if (it != m.end()) { 
     ++value; 
    } 
    map.insert(std::make_pair(key,value)); 
} 

Answer 3

После сортировки массива, вместо подсчета дубликатов, подсчитать количество переходов, где a[i-1] != a[i] && a[i] == a[i+1], который даст количество повторяющихся элементов. Однако вы должны соблюдать границы.

Answer 4

Вы найдете 3, потому что не проверяете, совпадает ли текущее число как дублирующее: первые 4, вы найдете дубликат, а второй тоже. Вы должны проверить, нет ли текущего числа в начале массива. Если да, то это уже считается дубликатом, поэтому нет необходимости продолжать, вы можете перейти к следующему номеру

int main() { 
    const int num_elements = 12; 
    int numbers[num_elements] = { 2, 6, 7, 4, 5, 4, 1, 8, 9, 0, 7, 4 }; 


    for(int i = 0; i < num_elements; ++i){ 
     int oneCounterMax = 0; 
     bool notAlreadyCheck = true; 

     for(int j = 0; j < i-1; ++j) { 
      if (numbers[i] == numbers[j]){ 
       notAlreadyCheck = false; 
      } 
     } 
     if (notAlreadyCheck) {  
      for(int j = i + 1; j < num_elements; ++j) { 
       if((numbers[i] == numbers[j]) && (oneCounterMax < 1)) { 
        ++numduplicates; 
        ++oneCounterMax; 
       }  
      } 
     } 
    }  
    cout << numduplicates << endl; 
} 

Answer 5

Сначала вы должны отсортировать массив, а затем пропустить повторяющиеся элементы и увеличить значение numduplicates

int main() { 
    const int num_elements = 12; 
    int numbers[num_elements] = { 2, 6, 7, 4, 5, 4, 1, 8, 9, 0, 7, 4 }; 

    sort(numbers,numbers+12);//sorting 
    int numduplicates = 0; 
    for(int i = 0; i < num_elements; ++i){ 
     if((i+1)<num_elements && numbers[i] == numbers[i+1]) { 
      ++numduplicates; 
      while((i+1)<num_elements && numbers[i] == numbers[i+1]) 
       i++; 
     }  
    }  
    cout << numduplicates << endl; 
} 

Answer 6

Если разрешено сортировать массив, вы можете написать что-то вроде этого:

std::sort(numbers, numbers + num_elements); 

int k = 0; 
while (k < num_elements - 1) { 
    int i = 1; 
    while ((k + i < num_elements) && (numbers[k + i] == numbers[k])) 
     i++; 
    if (i > 1) 
     ... // numbers[k] is a duplicate with multiplicity i 
    k += i; 
} 

Answer 7

Первый Рассортируйте ARRA y, а затем итерации по этому отсортированному массиву. Используйте флаг bool, чтобы сохранить текущее состояние о том, был ли этот номер подсчитан как дублирующийся номер.

#include <iostream> 
#include <algorithm> 
using namespace std; 

int main() 
{ 
    const int num_elements = 12; 
    int numbers[num_elements] = { 2, 6, 7, 4, 5, 4, 1, 8, 9, 0, 7, 4 }; 

    std:sort(numbers, numbers+num_elements); 
    int duplicate_count = 0; 
    bool duplicate = false; 
    for(int i = 1; i < num_elements; i++) 
    { 
     if(numbers[i] != numbers[i-1]) 
      duplicate = false; 
     else if(numbers[i] == numbers[i-1] && !duplicate) 
     { 
      duplicate_count++; 
      duplicate = true; 
     } 
    } 
    cout << "duplicate count: " << duplicate_count << endl; 
    return 0; 
} 

Answer 8

Большинство ответов достаточно хорошо, но не стремится слишком далеко от вашего решения, есть и умный трюк, чтобы быть были !:

#include <iostream> 
using namespace std; 

int main() { 
    const int num_elements = 12; 
    int numbers[num_elements] = { 2, 6, 7, 4, 5, 4, 1, 8, 9, 0, 7, 4 }; 

    unsigned int numduplicates = 0; 
    for (int i = 0; i < num_elements; ++i) { 
     int counter = 0; // changed name 
     for (int j = i + 1; j < num_elements; ++j) { 
      if (numbers[i] == numbers[j]) { // changed condition 
       ++counter; // only increment counter 
      } 
     } 

     if (counter == 1) { // added if statement 
      ++numduplicates; 
     } 
    } 
    cout << numduplicates << endl; 
} 

Вместо подсчет только один из дубликатов (с oneCounterMax), мы считаем все из них. Позже мы проверяем, если число, которое мы рассчитывали именно 1.

Это делает 2 вещи:

• Мы насчитали по крайней мере 1 дубликат, так Eсть дубликат текущего номера. но ...
• Если мы подсчитали более 1 дубликата, мы не увеличиваем дублирующийся счетчик, потому что это уже будет сделано позже на нашей итерации, когда мы снова подсчитаем второй дубликат.

Answer 9

Звучит как домашнее задание, и в этом случае ваш учитель может быть недоволен этим подходом, хотя он не использует vector.

Учитывая входной массив:

int numbers[num_elements] = { 2, 6, 7, 4, 5, 4, 1, 8, 9, 0, 7, 4 }; 

Вы можете найти уникальный размер массива путем использования set, так как set:

ассоциативный контейнер, который содержит упорядоченный набор объекты типа Key

В C++ 14 вы можете построить set так:

const auto numduplicates = num_elements - set<int>(cbegin(numbers), cend(numbers)).size(); 

Live Example

В C++ 11 вы можете построить set так:

const auto numduplicates = num_elements - set<int>(numbers, next(numbers, num_elements)).size(); 

И перед тем, что вы мог бы построить set следующим образом:

const auto numduplicates = num_elements - set<int>(numbers, numbers + num_elements).size(); 

Answer 10

реализация Простейшее для отсортированного массива:

#include <iostream> 
#include <algorithm> 

int main() 
{ 
    int numbers[] = { 2, 6, 7, 4, 5, 4, 1, 8, 9, 0, 7, 4 }; 

    auto b = std::begin(numbers); 
    auto e = std::end(numbers); 
    std:sort(b, e); 
    auto ne = std::unique(b, e); 
    std::cout << "duplicates:" << std::distance(ne, e) << std::endl; 
} 

или одну петлю:

#include <iostream> 
#include <algorithm> 

int main() 
{ 
    int numbers[] = { 2, 6, 7, 4, 5, 4, 1, 8, 9, 0, 7, 4 }; 

    auto b = std::begin(numbers); 
    auto e = std::end(numbers); 
    std:sort(b, e); 

    int dups = 0; 
    int v = *b++; 
    for(auto it = b; it != e; ++it) { 
     if(v != *it) v = *it; 
     else ++dups; 
    } 
    std::cout << "duplicates:" << dups << std::endl; 
}