存儲器限制在C++

int Solution::solve(vector<int> &A) 
{ 
    sort(A.begin(), A.end()); 
    map<int, int>ma; 
    int m; 
    for (int i = 0; i<A.size(); i++) 
     ma[A[i]] = 1; 
    for (int i = 0; i<A.size(); i++) 
     ma[A[i]]++; 
    if (A.size() == 1 && A[0] == 0) 
     return 1; 
    if (ma[A[0]] == (A.size() + 1)) 
     return -1; 
    for (int i = 0; i<A.size(); i++) 
    { 
     if (ma[A[i]]>2 && ma[A[i]]>0) 
     { 
      m = A.size() - (i + 1) - (ma[A[i]] - 2); 
      ma[A[i]] = -1; 

     } 
     if (ma[A[i]] == 2) 
      m = A.size() - (i + 1); 
     if (m == A[i]) 
     { 

      return 1; 
     } 
    } 
    return -1; 
}

給定一個整數數組超過，發現如果一個整數p的陣列，使得所述陣列中大於p的整數的數目等於至p 如果這樣的整數被發現返回1，否則在存在返回-1。 A是用戶輸入的矢量。存儲器限制在C++

我在interviewBit.com 寫這個程序是表示MEMORY上限超出如何優化這個代碼，我已經採用陣列，矢量試過，unordered_map代替圖則示出了分段故障

陣列可以有重複的元素以及負的整數ALSO 我已經使用地圖跟蹤每一個元素被重複了多少遍

來源

2017-09-15 WRICK

檢查關。如果您正在尋找反饋工作代碼，考慮在HTTPS發佈：//codereview.stackexchange .com /代替。 –

你不應該在這裏問這個問題！ –

你爲什麼需要地圖？從結束開始排序後。最後一個值沒有比它更大的成員 - 所以它應該是0來匹配條件。下一個應該是1，接下來應該是2 ...直到找到匹配或富指數0. –

無需使用地圖。排序後;只需從數組的末尾開始，對元素進行計數並將該計數與即將到來的元素進行比較。

更新：甚至更好 - 按降序對數組進行排序，並檢查任何元素是否等於其索引。

來源

2017-09-15 15:08:17 Sergei

@Mohsen_Fatemi通過不使用額外內存來優化代碼 - 它如何回答問題？ – Sergei

這個問題背後的想法是如何找出有多少項大於數組中的給定值，而不使用任何額外的內存。

一旦數組被排序，這很容易實現：從數組大小中減去當前基於一位的位置可以給出答案。

因此，您可以通過對數組進行排序來解決此問題，然後再行走一次，並檢查每個位置是否爲a[i] == a.size()-i-1。

注意：如果您在數組中允許相同的數字，問題可能會變得更加困難。在這種情況下，您需要在檢測到相同範圍的開始後繼續向上走陣列。

來源

2017-09-15 15:10:30 dasblinkenlight

將nth_element與二分查找相結合可能會在O（N）中得到平均結果（〜2N + logN）。提前

完全未經測試代碼：

auto start = v.begin(); 
auto last = v.end(); 

while(start != last) { 

    auto half = (std::distance(start, last)/2); 
    auto median = start + half; 
    std::nth_element(start, median, last); 
    auto med = *median; 

    if (med > half) { 
     if (*median > std::distance(median, v.end())) 
     return -1; // early out 
     last = median; 
    } else { 
     if (*median < std::distance(median, v.end())) 
     return -1; // early out 
     start = median; 
    }  
} 

if (*start == std::distance(start, v.end()) 
    return 1; 
return -1;

TODO：測試，測試通過一個

來源

2017-09-15 17:09:46 Surt

存儲器限制在C++

回答

相關問題