数组中有多少个数字小于或等于 x？

Question

给定一个整数 n 和数组 a，我需要为每个 i 找到, 1≤ i ≤ n, 左边有多少个元素小于等于a_我

示例：

    5 
    1 2 1 1 2

输出

    0 1 1 2 4

我可以在 O(N²) 中完成，但我想问一下有没有什么办法可以更快，因为 N 非常大 (N ≤ 10⁶)?

Answer 1

您可以使用线段树，您只需要使用称为范围树的修改版本。范围树允许矩形查询，所以你可以让维度是索引和值，然后问“什么值大于 x，索引在 1 和 n 之间？” 假设某些常见的优化，可以在 O(log n) 中完成查询。

无论哪种方式，O(N^2) 都完全适合 N < 10^6。

Answer 2

是的，与 O(N^2) 即 O(NlogN) 相比，它可以以更好的时间复杂度完成。我们可以使用分而治之算法和树的概念。

想看上面提到的两个算法的源码？？？ Visit Here .

我认为O(N^2)应该是最坏的情况。在这种情况下，我们将不得不至少遍历数组两次。我试过 O(N^2):

import java.io.*; import java.lang.*;

public class GFG {

public static void main (String[] args) {
    int a[]={1,2,1,1,2};
   
   
   int i=0;
   int count=0;
   int b[]=new int[a.length];
   for(i=0;i<a.length;i++)
   {
       for(int c=0;c<i;c++)
       {
       if(a[i]>=a[c])
       {
            count++;
       }
         }
       b[i]=count;
       count=0;
   }
   for(int j=0;j<b.length;j++)
        System.out.print(b[j]+" ");
}`

Answer 3

我喜欢考虑更大的数组来解释，所以我们考虑下面的数组，

2, 1, 3, 4, 7, 6, 5, 8, 9, 10, 12, 0, 11, 13, 8, 9, 12, 20, 30, 60

最简单的方法是比较一个元素和它左边的所有元素。天真的方法具有 O(n^2) 的复杂性，这使得它对大数组没有用。

如果你仔细看这个问题，你会发现其中的规律，规律就是Rather than comparing with each left element of an element we can compare first and last value of a range!。等一下这里的范围是多少？

这些数字可以看作是范围，可以通过从左到右遍历数组来创建范围。范围如下，

[2]、[1, 3, 4, 7]、[6]、[5, 8, 9, 10, 12]、[0, 11, 13]、[8, 9, 12, 20, 30, 60]

让我们开始从左到右遍历数组，看看我们如何创建这些范围，以及这些范围如何减少查找元素左侧所有较小或相等元素的工作量。

索引 0 的左侧没有要比较的元素，因此我们从索引 1 开始，此时我们没有任何范围。现在我们比较索引 1 和索引 0 的值。值 1 不小于或等于 2，所以这是非常重要的比较，由于这个比较我们知道之前的范围应该在这里结束，因为现在数字不是按顺序排列的，在这一点上我们得到第一个范围 [2]，它仅包含单个元素，并且小于或等于索引 1 处元素左侧的元素数是 zero.

在索引 2 处继续从左到右遍历，我们将其与索引 1 处的前一个元素进行比较，现在值 1 <= 3 这意味着新范围未在此处开始我们仍然处于从索引 1 开始的相同范围内。因此，要找到有多少元素小于或等于，我们必须首先计算当前范围 [1, 3) 中的元素数量，在这种情况下只有一个元素，此时我们只有一个已知范围 [2] 并且它有一个小于 3 的元素，因此索引 2 处元素左侧小于或等于元素的总数 = 1 + 1 = 2。对于其余元素，这可以以类似的方式完成，我想直接跳转到索引 6，即数字 5、

在索引 6 处，我们已经准备好发现三个范围 [2]、[1, 3, 4, 7]、[6] 但只有两个范围 [2] 和 [1, 3, 4, 7] 应予考虑。我如何提前知道范围 [6] 没有比较就没有用，将在本说明的最后说明。要查找左侧小于或等于元素的数量，我们可以看到第一个范围 [2] 只有一个元素且小于 5，第二个范围具有第一个元素 1，该元素小于 5比 5 但最后一个元素是 7 并且它大于 5，所以我们不能考虑范围的所有元素，而是我们必须在这个范围内找到 upper bound 来找到如何我们可以考虑的许多元素和 upper bound 可以通过 binary search 找到，因为 range is sorted ，所以这个范围包含三个小于或等于 5 的元素 1, 3, 4 .两个范围中小于或等于 5 的元素总数为 4 并且索引 6 是当前范围的第一个元素，并且当前范围中它的左侧没有元素，因此总计计数 = 1 + 3 + 0 = 4.

关于这个解释的最后一点是，我们必须将 store ranges in tree structure with their first value as key and value of the node 应该是 array of pair of first and last index of range。我将在这里使用std::map。需要这个树结构，这样我们就可以在logarithmic时间内通过查找upper bound找到所有first 元素小于或等于我们当前元素的范围。这就是原因，我在比较索引 6 处的元素时提前知道，已知时间的三个范围都不是可观的，只有两个是可观的。
解决方案的复杂性是，

O(n)在数组中从左到右移动，plus
O(n (m + log m)) 用于在 std::map 中为每个元素查找 upper bound 并比较 m 个范围的最后一个值，这里 m 是特定时间已知的范围数，plus
O(log q) 用于在范围内查找 upper bound 如果 rage 最后一个元素大于数字，这里 q 是特定范围内的元素数（可能需要也可能不需要）

#include <iostream>

#include <map>
#include <vector>

#include <iterator>
#include <algorithm>

unsigned lessThanOrEqualCountFromRage(int num, const std::vector<int>& numList,
                                      const std::map<int,
                                      std::vector<std::pair<int, int>>>& rangeMap){

    using const_iter = std::map<int, std::vector<std::pair<int, int>>>::const_iterator;

    unsigned count = 0;
    const_iter upperBoundIt = rangeMap.upper_bound(num);

    for(const_iter it = rangeMap.cbegin(); upperBoundIt != it; ++it){

        for(const std::pair<int, int>& range : it->second){

            if(numList[range.second] <= num){
                count += (range.second - range.first) + 1;
            }
            else{
                auto rangeIt = numList.cbegin() + range.first;

                count += std::upper_bound(rangeIt, numList.cbegin() +
                                          range.second, num) - rangeIt;
            }
        }
    }

    return count;
}


std::vector<unsigned> lessThanOrEqualCount(const std::vector<int>& numList){

    std::vector<unsigned> leftCountList;
    leftCountList.reserve(numList.size());

    leftCountList.push_back(0);

    std::map<int, std::vector<std::pair<int, int>>> rangeMap;

    std::vector<int>::const_iterator rangeFirstIt = numList.cbegin();

    for(std::vector<int>::const_iterator it = rangeFirstIt + 1, endIt = numList.cend();
        endIt != it;){

        std::vector<int>::const_iterator preIt = rangeFirstIt;

        while(endIt != it && *preIt <= *it){

            leftCountList.push_back((it - rangeFirstIt) +
                                    lessThanOrEqualCountFromRage(*it,
                                                                 numList, rangeMap));

            ++preIt;
            ++it;
        }

        if(endIt != it){

           int rangeFirstIndex = rangeFirstIt - numList.cbegin();
           int rangeLastIndex = preIt - numList.cbegin();

           std::map<int, std::vector<std::pair<int, int>>>::iterator rangeEntryIt =
                   rangeMap.find(*rangeFirstIt);

           if(rangeMap.end() != rangeEntryIt){

               rangeEntryIt->second.emplace_back(rangeFirstIndex, rangeLastIndex);
           }
           else{

               rangeMap.emplace(*rangeFirstIt, std::vector<std::pair<int, int>>{
                                    {rangeFirstIndex,rangeLastIndex}});
           }

           leftCountList.push_back(lessThanOrEqualCountFromRage(*it, numList,
                                                                rangeMap));

           rangeFirstIt = it;
           ++it;
        }
    }

    return leftCountList;
}

int main(int , char *[]){

    std::vector<int> numList{2, 1, 3, 4, 7, 6, 5, 8, 9, 10, 12,
                             0, 11, 13, 8, 9, 12, 20, 30, 60};

    std::vector<unsigned> countList = lessThanOrEqualCount(numList);

    std::copy(countList.cbegin(), countList.cend(),
              std::ostream_iterator<unsigned>(std::cout, ", "));

    std::cout<< '\n';
}

输出:
0, 0, 2, 3, 4, 4, 4, 7, 8, 9, 10, 0, 11, 13, 9, 11, 15, 17, 18, 19,

数组中有多少个数字小于或等于 x？

How many number are less than or equal than x in an array?

c++

algorithm

time-complexity

示例：

输出