爲什麼這段代碼超出了時間限制？

-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等方面都很優秀。 –

感謝您澄清這一點！ –

爲什麼這段代碼超出了時間限制？

回答

相關問題