Algorithms to Count How Many Numbers Are Smaller Than the Curren

  • 时间:2020-09-10 13:27:27
  • 分类:网络文摘
  • 阅读:90 次

Given the array nums, for each nums[i] find out how many numbers in the array are smaller than it. That is, for each nums[i] you have to count the number of valid j’s such that j != i and nums[j] < nums[i].

Return the answer in an array.

Example 1:
Input: nums = [8,1,2,2,3]
Output: [4,0,1,1,3]
Explanation:
For nums[0]=8 there exist four smaller numbers than it (1, 2, 2 and 3).
For nums[1]=1 does not exist any smaller number than it.
For nums[2]=2 there exist one smaller number than it (1).
For nums[3]=2 there exist one smaller number than it (1).
For nums[4]=3 there exist three smaller numbers than it (1, 2 and 2).

Example 2:
Input: nums = [6,5,4,8]
Output: [2,1,0,3]

Example 3:
Input: nums = [7,7,7,7]
Output: [0,0,0,0]

Constraints:
2 <= nums.length <= 500
0 <= nums[i] <= 100

Hints:
Brute force for each array element.
In order to improve the time complexity, we can sort the array and get the answer for each array element.

We can solve this problem using bruteforce algorithm or the binary search.

Bruteforce Algorithm to Count the Elements smaller than Current

The most intuitive solution is to bruteforce each number and then count the number of elements smaller than the current. This requires O(N^2) square complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> r;
        for (const auto &n: nums) {
            int cnt = 0;
            for (const auto &m: nums) {
                if (m < n) cnt ++;
            }
            r.push_back(cnt);
        }
        return r;
    }
};
class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> r;
        for (const auto &n: nums) {
            int cnt = 0;
            for (const auto &m: nums) {
                if (m < n) cnt ++;
            }
            r.push_back(cnt);
        }
        return r;
    }
};

Binary Search Algorithm to Count the Numbers Smaller than Current

To improve the solution, we can sort the numbers, then we can use binary search Algorithm to find the lower bound of the number. This reduces the complexity to O(N LogN).

In C++, we can use the std::lower_bound to return the first position (iterator) of the current number in the sorted array.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> r;
        vector<int> data(begin(nums), end(nums));
        sort(begin(data), end(data));
        for (const auto &n: nums) {
            int cnt = lower_bound(begin(data), end(data), n) - begin(data);
            r.push_back(cnt);
        }
        return r;
    }
};
class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> r;
        vector<int> data(begin(nums), end(nums));
        sort(begin(data), end(data));
        for (const auto &n: nums) {
            int cnt = lower_bound(begin(data), end(data), n) - begin(data);
            r.push_back(cnt);
        }
        return r;
    }
};

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
数学题——一种余数相同的问题  周末妈妈从家送巧巧去学校学钢琴  平角就是一条直线判断对错  29957四舍五入到百位、千位、万位是多少?  已知被除数,除数,商与余数的和是235,已知商是27,余数是6,求除数。  图中几条直线、几条射线、几条线段?  滞尘是什么意思?  冬冬是2008年2月29日出生的,到2016年2月29日他一共过了几个生日?  饮料架上放有大、中、小三种包装的饮料  有一架天平和一个50克的砝码,如果要得到150克糖果 
评论列表
添加评论