我们能否找到线性时间复杂度为 O(n) 的数组中每个元素的秩？

Question

我正在尝试解决this Leetcode problem，其中要求解决：

Given an array of integers arr, replace each element with its rank. For example:

Input: arr = [40,10,20,30]
Output: [4,1,2,3]
Explanation: 40 is the largest element. 10 is the smallest. 20 is the second smallest. 30 is the third smallest.

我的代码如下：

    class Solution {
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        multimap<int, int> numbeToIndexrMap;
        int size = arr.size();
        vector<int> rank(size, 10);
        for(int i = 0; i < size; ++i){
            numbeToIndexrMap.insert({arr[i], i});
        }
        int rankIndex = 1;
        int previous = INT_MIN;
        for(auto i = numbeToIndexrMap.begin(); i != numbeToIndexrMap.end(); ){
            int currentNumber = i -> first;
            rank[i->second] = rankIndex;
            ++i;
            if(i != numbeToIndexrMap.end() && i -> first != currentNumber) ++rankIndex;
        }
        return rank;
    }
};

我发现我们可以用Sorting/Map来解决这个时间复杂度为O(NlogN)的问题。我的问题是我们是否可以在线性时间 O(n) 内做到这一点？

Answer 1

即使在该问题的提示部分，他们也希望我们对数组进行排序，这本身就需要 O(nlog(n)) 的时间复杂度。在这里，排序并不重要，而是解决方案的必要部分。所以与众不同的是你如何从排序的数组中搜索排名。天真的方法是使用 linear search O(n) 在排序数组中找到原始数组的 each 个元素的 index。所以总体时间复杂度为 O(n*n)。最好的方法是使用 binary search O(log(n)) 在排序数组中找到原始数组的每个元素的索引。所以总的时间复杂度是 O(n*log(n)).

我们能否找到线性时间复杂度为 O(n) 的数组中每个元素的秩？

Can we find rank of each element in array with Linear Time Complexity O(n)?

arrays

sorting

hashmap

ranking

data-structures