このコードは時間制限を超えていますか？

Question

配列内で奇数回発生する要素を選択したいと考えています。私はヒープからINT_MAXサイズの配列を宣言し、セグメンテーション違反でそれをやめましたが、今はそれがトールを与えています。同じアルゴリズムを使って何ができますか？

/* C++ code to find out the element that occurs odd number of times, given there is only one such element in the array */ 

#include <bits/stdc++.h> 

using namespace std; 

int main(){ 
    int n, i; 
    cin >> n; 
    int arr[n]; 
    for (i = 0; i < n; i++) 
     cin >> arr[i]; 
    int* a = new int[INT_MAX]; // declared a dynamic array 
    fill_n(a, INT_MAX, 0); //initialised to 0 
    for (i = 0; i < n; i++) { 
     a[arr[i]]++; // for every particular value, that corresponding index value increases 
    } 

    for (i = 0; i < n; i++) { 
     if(a[arr[i]] % 2 == 1) { //if that corresponding index value is odd, that's the answer 
      cout << arr[i]; 
      break; 
     } 
    } 
     delete[] a; 
return 0;  
} 

Answer 1

この：

int* a = new int[INT_MAX]; // declared a dynamic array 

は20億の整数、ストレージのすなわち、8ギガバイトを割り当てる予定です。次にあなたはランダムにアクセスします。あなたのシステムは、そのような多くのストレージを割り当てるのに苦労するかもしれませんし、できるだけ多くのメモリを実際に読み書きすることは不可能かもしれません。

あなたは同じアルゴリズムを使用して行うことができますどのような

を尋ねましたか？

何もありません。このアルゴリズムは不十分であり、実用的な方法で使用することはできません。別のアルゴリズムが必要になります。