Проверка дубликатов в массиве с помощью цикла for

Question

Я пытаюсь проверить, есть ли повторяющееся целое число в массиве пользовательского ввода. Проблема в том, что проверка дубликата не работает должным образом, и я понятия не имею, почему он не показывает желаемый результат. Ниже приведен код:

#include <iostream>

using namespace std;

int main()
{
    int length;
    int arrValue;

    cout << "Enter the length : ";
    cin >> length;

    int *arr = new int[length];

    cout << "Enter " << length << " integers for array : ";

    for(int i = 0; i < length; i++)
    {
        cin >> arr[i];
    }

    cout << "Array : ";

    for(int i = 0; i < length; i++)
    {
        arrValue = arr[i];
    
        for(int k = i + 1; k < length; k++)
        {
            if(arr[i] == arr[k])
            {
                cout << "Duplicate found" << endl;
                break;
            }
            else
            {
                cout << arrValue << " ";
            }
        }
    }

   delete[] arr;
}

Текущий результат (при условии отсутствия дубликатов при вводе пользователем):

Enter the length: 5
Enter 5 integers for array : 5 4 3 2 1
Array : 5 5 5 5 4 4 4 3 3 2

Ожидаемый результат (при условии отсутствия дубликатов в пользовательский ввод):

Enter the length: 5
Enter 5 integers for array : 5 4 3 2 1
Array : 5 4 3 2 1

Текущий результат (при условии дублирования в пользовательском вводе):

Enter the length: 5
Enter 5 integers for array : 5 4 4 2 1
Array : 5 5 5 5 Duplicate found 4 4 3

Ожидаемый результат (при условии дублирования в пользовательский ввод):

Enter the length: 5
Enter 5 integers for array : 5 4 4 2 1
Array : Duplicate found

Я считаю, что мои циклы являются источником проблемы. Текущий результат выводится 10 раз, и я не понимаю, почему будет появляться так много одинаковых чисел.

Обратите внимание, что я пытаюсь применить проверку, используя только l oop, а не из стандартной библиотеки C ++.

Answer 1

Это не работает, потому что вы пытаетесь печатать одно и то же значение каждый раз, когда находите другое. У меня есть решение с еще одним массивом, который будет хранить этот массив. Он также будет работать с одним массивом.

#include <iostream>

using namespace std;

int main()
{
    int length;
    int arrValue;

    cout << "Enter the length : ";
    cin >> length;

    int *arr = new int[length];
    int *noDuplicateArr = new int[length];

    cout << "Enter " << length << " integers for array : ";

    for(int i = 0; i < length; i++)
        cin >> arr[i];

    cout << "Array : ";

    bool duplicateFound = false;
    int noDuplicateArrLen = 0;

    for(int i = 0; i < length && !duplicateFound; i++)
    {
        arrValue = arr[i];

        int k;

        for(k = i + 1; k < length; k++)
        {
            if(arrValue == arr[k])
            {
                duplicateFound = true;
                break;
            }
        }

        if (k == length)
            noDuplicateArr[noDuplicateArrLen++] = arrValue;
    }

    if (duplicateFound)
    {
        cout << "Duplicate found";
    }
    else
    {
        for (int i = 0; i < noDuplicateArrLen; i++)
        {
            cout << noDuplicateArr[i] << " ";
        }
    }

    delete[] arr;
    delete[] noDuplicateArr;
}

Вот версия с одним массивом:

#include <iostream>

using namespace std;

int main()
{
    int length;
    int arrValue;

    cout << "Enter the length : ";
    cin >> length;

    int *arr = new int[length];

    cout << "Enter " << length << " integers for array : ";

    for(int i = 0; i < length; i++)
        cin >> arr[i];

    cout << "Array : ";

    bool duplicateFound = false;
    int noDuplicateArrLen = 0;

    for(int i = 0; i < length && !duplicateFound; i++)
    {
        arrValue = arr[i];

        int k;

        for(k = i + 1; k < length; k++)
        {
            if(arrValue == arr[k])
            {
                duplicateFound = true;
                break;
            }
        }

        if (k == length)
            arr[noDuplicateArrLen++] = arrValue;
    }

    if (duplicateFound)
    {
        cout << "Duplicate found";
    }
    else
    {
        for (int i = 0; i < noDuplicateArrLen; i++)
        {
            cout << arr[i] << " ";
        }
    }

    delete[] arr;
}

Answer 2

Проблема в вашем коде заключается в том, что вы распечатываете каждый элемент массива каждый раз, когда конкретный элемент не соответствует другому элементу. Кажется, вы хотите только распечатать, обнаружены ли какие-либо повторяющиеся значения. Для этого вы можете использовать флаг bool, чтобы указать, дублируется ли какой-либо элемент:

bool found_dup = false;
for(int i = 0; i < length; i++)
    for(int k = i + 1; k < length; k++)
        if(arr[i] == arr[k])
        {
             found_dup = true;
             break;
        }
        //  else: don't print anything yet

, а затем в конце распечатать массив:

if (found_dup)
    std::cout << "Duplicate found";
else
    for(int i = 0; i < length; i++)
        std::cout << arr[i] << " ";

Answer 3

Пожалуйста, измените условие if на что-то вроде этого.

cout << "Enter the length : ";
    cin >> length;

    int *arr = new int[length];

    cout << "Enter " << length << " integers for array : ";

    for(int i = 0; i < length; i++)
    {
        cin >> arr[i];
    }

    cout << "Array : ";

    for(int i = 0; i < length; i++)
    {
        arrValue = arr[i];
    
        for(int k = i + 1; k < length; k++)
        {
            if(arrValue == arr[k])             //change here.
            {
                cout << "Duplicate found" << endl;
                break;
            }
            else
            {
                cout << arrValue << " ";
            }
        }
    }

   delete[] arr;
}

Я бы также предложил использовать структуру данных карты. Карта позволяет подсчитывать частоту чисел и таким образом обнаруживать дубликаты за линейное время.

map<int, int> m; // specify the key-value data-type.

for(int i = 0;i<length;i++)
{
     m[arr[i]]++;
}

map<int, int>::iterator it; // an iterator to iterate over the datastructure.
for(it = m.begin();it!=m.end();it++)
{
     if(it->second>1)             //it->second refers to the value(here, count).
     {
          cout<<it->first<<" ";   //it->first refers to the key.
     }
}

Answer 4

Ваши циклы на самом деле повторяются n-1 раз для первого элемента, n-2 раза для второго элемента и т.д. c., Где n - длина вашего массива. Вот почему для массива из 5 элементов вы напечатали 5 4 раза.

Но, как правило, если целью является обнаружение дубликатов в массиве, эта стратегия не лучшая. Обратите внимание, что имея примерный массив 4 3 4, при текущем подходе вы правильно обнаружите для первого 4, что третий элемент также 4, но как только вы перейдете к третьему элементу, он будет отмечен как ОК, поскольку он не проверяется с первым элементом.

Вы можете рассмотреть другую стратегию: создать еще один массив размером n. Затем выполните итерацию по исходному массиву и для каждого элемента проверьте, есть ли этот элемент уже в новом массиве. Если вы обнаружите присутствие, вы можете вызвать событие duplicate. В противном случае вы можете добавить этот элемент в массив.

Answer 5

Вы можете выполнить программу более расширенным способом (где вам не нужно определять длину вручную - обратите внимание на объяснение, данное в виде комментариев в коде):

#include <iostream>    // for input/output operation
#include <vector>      // for dynamic array management
#include <sstream>     // to split the user inputs and assign them to the vector
#include <algorithm>   // to sort the vector
#include <string>      // to work with getline()

// using this statement isn't recommended, but for sake of simplicity
// and avoiding the use of std:: everywhere temporarily (for small programs)
using namespace std;

int main(void) {
    vector<int> numbers;
    vector<int> duplicates;
    string input;
    int temp;

    // getting the user input as string
    cout << "Enter the numbers: ";
    getline(cin, input);

    stringstream ss(input);

    // splitting the user input string into integers and assigning
    // them into the vector
    while (ss >> temp)
        numbers.push_back(temp);

    // sorting the vector in increasing order
    sort(numbers.begin(), numbers.end());

    // getting the unique numbers (which are not repeated)
    cout << "Unique numbers: ";

    for (size_t i = 0, len = numbers.size(); i < len; i++) {
        if (temp == numbers[i])
            // if found a duplicate, then push into the 'duplicates' vector
            duplicates.push_back(temp);
        else
            cout << numbers[i] << ' ';

        temp = numbers[i];
    }

    // getting the duplicates
    cout << "Total duplicates: ";
    for (size_t i = 0, len = duplicates.size(); i < len; i++)
        cout << duplicates[i] << ' ';
    cout << endl;

    return 0;
}

Будет выведено что-то например:

Enter the numbers: 1 4 8 9 3 2 3 3 2 1 4 8
Unique numbers: 1 2 3 4 8 9 
Total duplicates: 1 2 3 3 4 8