Подсчет количества различных чисел в массиве

Question

Чтобы найти количество различных чисел в массиве из l го по r го индекса, я написал блок кода, как:

int a[1000000]; 
//statements to input n number of terms from user in a.. along with l and r 

int count=r-l+1; //assuming all numbers to be distinct 
for(; l<=r; l++){ 
    for(int i=l+1; i<=r; i++){ 
     if(a[l]==a[i]){ 
      count--; 
      break; 
     } 
    } 
} 
cout<<count<<'\n'; 

Объяснение Для того массив говорят, a = 5 6 1 1 3 2 5 7 1 2 из десяти элементов. Если мы хотим проверить количество различных чисел между [1] и [8], которое является вторым и девятым элементами (включая оба), логика, которую я попытался реализовать, сначала примет значение count = 8 (количество элементов), а затем он начинается с символа [1], который равен 6, и проверяет на наличие других 6 после него, если он найдет, он уменьшает счет на единицу и переходит к следующему номеру в строке. Таким образом, если после этого произойдет еще 6, это не будет включаться дважды.

Задача Я пробовал небольшие тестовые чехлы, и он работает. Но когда я пытался с большими данными, это не сработало, поэтому я хотел знать, где моя логика потерпит неудачу?

Более крупные данные, как и в других частях программы, а затем используются. Который дал неправильный вывод

Answer 1

Вы сказали, что не возражали против другого решения. Так вот оно. Он использует set - структуру, в которой хранятся только уникальные элементы. Кстати, по более крупным данным - он будет намного быстрее, чем решение с двумя циклами.

set<int> a1; 
    for (int i = l; i <= r; i++) 
    { 
     a1.insert(a[i]); 
    } 
    cout << a1.size(); 

Answer 2

Вы можете попробовать использовать std::set

Основная идея заключается в том, чтобы добавить все элементы в свой новый набор, а просто вывести размер вашего набора.

#include <iostream> 
#include <vector> 
#include <set> 

using namespace std; 

int main() 
{ 
    int l = 1, r = 6; 
    int arr[] = {1, 1, 2, 3, 4, 5, 5, 5, 5}; 
    set<int> s(&arr[l], &arr[r + 1]); 
    cout << s.size() << endl; 

    return 0; 
} 

Answer 3

Вот ответ, который не использует std::set, хотя это решение, вероятно, проще.

#include <algorithm> 
#include <vector> 

int main() 
{ 
    int input[10]{5, 6, 1, 1, 3, 2, 5, 7, 1, 2}; //because you like raw arrays, I guess? 

    std::vector<int> result(std::cbegin(input), std::cend(input)); //result now contains all of input 
    std::sort(std::begin(result), std::end(result)); //result now holds 1 1 1 2 2 3 5 5 6 7 
    result.erase(std::unique(std::begin(result), std::end(result)), std::end(result)); //result now holds 1 2 3 5 6 7 
    result.size(); //gives the count of distinct integers in the given array 
} 

Здесь live on Coliru, если вы в этом.

-

EDIT: Вот, краткий вариант множества решения тоже.

#include <set> 

int main() 
{ 
    int input[10]{5, 6, 1, 1, 3, 2, 5, 7, 1, 2}; //because you like raw arrays, I guess? 

    std::set<int> result(std::cbegin(input), std::cend(input)); 
    result.size(); 
} 

Answer 4

Лично я бы просто использовать стандартные алгоритмы

#include<algorithm> 
#include <iostream> 

int main() 
{ 
    int arr[] = {1, 1, 2, 3, 4, 5, 5, 5, 5}; 
    int *end = arr + sizeof(arr)/sizeof(*arr); 

    std::sort(arr, end); 

    int *p = std::unique(arr, end); 

    std::cout << (int)(p - arr) << '\n'; 
} 

Это, очевидно, зависит от того разрешено изменять массив (любые дубликаты будут перемещены в конец arr). Но при необходимости создавать копию массива легко и работать над копией.

Answer 5

Первый вопрос, задаваемый с этим типом проблемы, - это возможный диапазон значений. если диапазон чисел N «достаточно мал», то вы можете использовать логический массив размером N, чтобы указать, присутствует ли число, соответствующее индексу. Вы повторяете от l до r, установив флаг, и если флаг еще не установлен, увеличивайте счетчик.

count = 0; 
for(int i=l; i<=r; i++) { 
    if (! isthere[arr[i]]) { 
     count++; 
     isthere[arr[i]] = TRUE; 
    } 
} 

С точкой зрения сложности, и этот подход и основанный на наборе O (N), но на этот раз быстрее, так как нет хеширования участвует. Для небольших N, например, для чисел между 0-255, скорее всего, это также, вероятно, будет менее интенсивным в памяти. Для больших N, например, если допустимы любые 32-битные целые числа, подход, основанный на наборе, более подходит.

Answer 6

В следующем процессе я даю процесс подсчета уникальных номеров. В этом методе вы просто получаете уникальные элементы в массиве. этот процесс обновит ваш массив значением мусора. Поэтому в этом процессе вы больше не сможете использовать этот массив (который мы будем использовать). Этот массив будет автоматически изменять размер с помощью отдельных элементов.

#include <stdio.h> 
#include <iostream> 
#include <algorithm> // for using unique (library function) 

int main(){ 

    int arr[] = {1, 1, 2, 2, 3, 3}; 

    int len = sizeof(arr)/sizeof(*arr); // finding size of arr (array) 

    int unique_sz = std:: unique(arr, arr + len)-arr; // Counting unique elements in arr (Array). 

    std:: cout << unique_sz << '\n'; // Printing number of unique elements in this array. 

    return 0; 
} 

Если вы хотите справиться с этой проблемой (о том, что я сказал ранее), вы можете следить за этим процессом. Вы можете справиться с этим, справив свой массив в другом массиве.

#include <stdio.h> 
#include <iostream> 
#include <algorithm> // for using copy & unique (library functions) 
#include <string.h> // for using memcpy (library function) 

int main(){ 

    int arr[] = {1, 1, 2, 2, 3, 3}; 
    int brr[100]; // we will copy arr (Array) to brr (Array) 

    int len = sizeof(arr)/sizeof(*arr); // finding size of arr (array) 

    std:: copy(arr, arr+len, brr); // which will work on C++ only (you have to use #include <algorithm> 
    memcpy(brr, arr, len*(sizeof(int))); // which will work on C only 

    int unique_sz = std:: unique(arr, arr+len)-arr; // Counting unique elements in arr (Array). 

    std:: cout << unique_sz << '\n'; // Printing number of unique elements in this array. 

    for(int i=0; i<len; i++){ // Here is your old array, that we store to brr (Array) from arr (Array). 
     std:: cout << brr[i] << " "; 
    } 

    return 0; 
}