c++ - 返回一个数组，该数组包含数组中小于或等于给定数组中元素的元素数

Question

我遇到了这个问题，想知道是否有更好的复杂性来解决这个问题。

例如

• 数组 a = [1,4,2,4]
• 数组 b = [3,5]

期望的输出 ==> [2, 4]

编辑:再举一个例子

• 数组 a = [1,4,2,4]
• 数组 b = [3, 1000000]

期望输出 ==> [2,4]

到目前为止，我发现和尝试的运行时间为 O(nlogn) + O(blogn) 和 O(n)。

O(nlogn) + O(blogn) 方法:

 int binarysearch(vector<int>arr, int l, int r, int target) 
 {
      int mid;
      while(l <= r)
      {
          mid = (r+l) / 2;

          if(arr[mid] > target)
              r = mid - 1;
          else
              l = mid + 1;
      }

      return r; 
 }

vector<int> counts(vector<int> a, vector<int> b)
{
    vector<int> result;
    sort(a.begin(), a.end()); // O(nlogn)

    for(auto i : b){
        int count = binarysearch(a, 0, a.size()-1, b); // b*O(log n) times
        result.push_back(count)
    }
    return result;
}

O(n) 方法:

vector<int> counts(vector<int> a, vector<int> b)
{
    vector<int> result;
    int maxi = *max_element(b.begin(), b.end()) + 1;
    int mymap[maxi] = {0};

    for(auto i : a) mymap[i]++;

    for(int i = 1; i < maxi; i++){
        mymap[i] = mymap[i] + mymap[i-1];
    }

    for(auto i : b){
        result.push_back(mymap[i]);
    }
    return result;
}

Answer 1

[I am] wondering if there could be a better complexity to solve the problem.

Time complexity.

O(n) approach:

不，不存在小于线性时间复杂度的解决方案。

也就是说，您的线性解决方案是不正确的。如果输入数组包含 1000000 或更大的值，或者负数，则您在 mymap 的范围之外访问并且行为未定义。此外，i <= 1000000也访问 mymap在最后一次迭代的边界之外。此外，int[1000000]太大而不能成为局部变量。在某些系统上，即使是一个这样的变量也可能导致堆栈溢出。