存储器限制在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++

回答

相关问题