найти элемент, который появляется один раз в массиве, когда другие появляются дважды

Question

Я написал код со сложностью o (n ^ 2). Я не смог найти ошибку. Моя идея состояла в том, чтобы сначала отсортировать массив, а затем начать с первого элемента, если второй следующий равен приращению i на 2, и когда Если условие не выполнено, элемент найден. Может кто-нибудь, пожалуйста, помогите мне. Заранее спасибо

#include<iostream>
using namespace std;

int main()
{
int arr[100];
int n,i,j,temp;
cin>>n;
for(i=0;i<n;i++)
{
    cin>>arr[i];
}
for(i=0;i<n;i++)
{
    for(j=0;j<n;j++)
    {
        if(arr[i]>arr[j])
        {
            temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }
    }
}
i=0;
for(j=i+1;j<n;j++)
{
    if(arr[i] == arr[j])
    {
        i=i+2;
    }
}
cout<<arr[i];
return 0;
}

Answer 1

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

    int arr[] = {/*Some array*/};
    int arrSize = sizeof(arr)/sizeof(int);
    //Lets sort the array
    for(int i=0;i<arrSize;i++)
    {
        for(int j=i;j<arrSize;j++)
        {
            if(arr[i]>arr[j])
            {
                int t=arr[i];
                arr[i]=arr[j];
                arr[j]=t;
            }
        }
    }

После сортировки массива мы можем увидеть различные сценарии ios, такие как:

int arr1[] = {1,1,2,2,3};
int arr2[] = {1,2,2,3,3};
int arr3[] = {1,1,2,3,3};

Мы должны разработать алгоритм так, чтобы он можно дифференцировать и легко манипулировать тремя сценариями ios. Пусть n будет нашим номером. Первый сценарий - проверить, не совпадает ли последний с предыдущим:

    if(arr[arrSize-1] != arr[arrSize-2]) //The last is not the same as the previous
    {
        n=arr[arrSize-1];
    }

Второй аналогичен первому:

    if(arr[0] != arr[1]) // The first element is not the same as the second
    {
        n = arr[0];
    }

Третий это тоже просто, нам просто нужно проверить, не равны ли два соседа среднему числу, это выглядит следующим образом:

        for(int i=1;i<arrSize-1;i++)
        {
            if(arr[i-1] != arr[i] && arr[i] != arr[i+1])
            {
                n=arr[i];
                break;
            }
        }

И поэтому полный код будет:

#include <iostream>
using namespace std;

int main()
{
    int arr[] = {1,2,3,4,2,3,1};
    int arrSize = sizeof(arr)/sizeof(int);
    //Lets sort the array
    for(int i=0;i<arrSize;i++)
    {
        for(int j=i;j<arrSize;j++)
        {
            if(arr[i]>arr[j])
            {
                int t=arr[i];
                arr[i]=arr[j];
                arr[j]=t;
            }
        }
    }
    int n;
    if(arr[0] != arr[1]) // The first element is not the same as the second
    {
        n = arr[0];
    }
    else if(arr[arrSize-1] != arr[arrSize-2]) //The last is not the same as the previous
    {
        n=arr[arrSize-1];
    }
    else //Lets search for a number such that its not the same as the numbers on the left and on the right
    {
        for(int i=1;i<arrSize-1;i++)
        {
            if(arr[i-1] != arr[i] && arr[i] != arr[i+1])
            {
                n=arr[i];
                break;
            }
        }
    }
    cout << n;
}

Второй путь (лучше).

Вот еще один способ решить эту проблему. Предположим, что у меня есть число n = 3, если я XORed его с 3, я получу 0, поэтому если у нас есть массив, скажем, arr [] = {1,2,1}, я сначала назначаю n = 0, затем XOR это с первым элементом (1), затем я XOR n со вторым элементом, а затем с третьим элементом. Что случится? Третий XOR отменит эффект первого, поэтому n будет равно 1. Пример кода:

#include <iostream>
using namespace std;

int main()
{
    int arr[] = {1,2,3,4,2,3,1};
    int arrSize = sizeof(arr)/sizeof(int);
    int n=0;
    for(int i=0;i<arrSize;i++)
    {
        n^=arr[i];
    }
    cout << n;
}

Этот код O (n).