为什么这段代码超出了时间限制？

-4

我想挑出数组中出现奇数次的元素。我从堆中声明了大小为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;  
}

来源

2017-08-08 Muskan

什么是操作系统和编译器？ –

你需要找到一种不同的方法。提示：当你对自己的数字进行异或时会发生什么？ – NathanOliver

这里有一个更好的问题：你为什么想要分配'INT_MAX'元素？ –

此：

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

会拨出2点十亿的整数，即8 GB的存储空间。你随后会随机访问的。你的系统可能很难分配那么多的存储空间，即使可能，也可能无法在任何时间限制内实际读取和写入大量内存。

你问

什么可以使用相同的算法来完成？

什么都没有。该算法不足，不能以实用的方式使用。你将需要一个不同的算法。

来源

2017-08-08 13:17:07

_“......在任何时间限制允许的情况下，实际上都不可能读取和写入太多内存。”_这究竟意味着什么？计算机程序是否定期读写超过8GB？谁设置了时间限制？它是在编译时还是执行时？ –

@AGNGazer：当人们说他们对于简单的问答式程序有“超出时间限制”时，这表明他们正在测验平台上执行它们，可能是在线编码测试或类似测试。这些测试通常运行在“小型”机器（也许是VM）上。有些程序使用超过8 GB的内存，但仍然需要相当长的时间（可能是一分钟或更长时间）才能用这么多的内存来做任何有用的事情。现代CPU上的原始存储器带宽大约为20 GB/s，但假设理想条件; OP的代码在缓存利用率，TLB等方面都很优秀。 –

感谢您澄清这一点！ –

为什么这段代码超出了时间限制？

回答

相关问题