leetcode：1365. 有多少小于当前数字的数字

题目来源

1365. 有多少小于当前数字的数字

题目描述

在这里插入图片描述

题目解答

暴力循环法

c++

vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
    vector<int> res;
    int cnt , curr;
    for (int i = 0; i < nums.size(); ++i) {
        cnt = 0;
        curr = nums[i];
        for (int j = 0; j < nums.size(); ++j) {
            if (i == j){
                continue;
            }
            if (curr > nums[j]){
                cnt++;
            }
        }
        res.emplace_back(cnt);
    }
    return res;
}

在这里插入图片描述

java

public static int[] soloution1(int [] array){
        int [] res = new int[array.length];
        for (int i = 0; i < array.length; i++) {
            int count = 0;
            for (int j = 0; j < array.length; j++){
                if (i != j){
                    if (array[j] < array[i]){
                        count++;
                    }
                }
            }
            res[i] = count;
        }
        return res;
    }

解答2：排序

c++

写法

class Solution {
public:
vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
    int len = nums.size();
    vector<pair<int, int>> sort_vec;
    for (int i = 0; i < len; ++i) {
        sort_vec.emplace_back(pair{
    nums[i], i});
    }
    std::sort(sort_vec.begin(), sort_vec.end());
    vector<int> res(len, 0);
    int prev = -1;
    for (int i = 0; i < len; ++i) {
        if (prev == -1 || sort_vec[i - 1].first != sort_vec[i].first){
            prev = i;
        }
        res[sort_vec[i].second] = prev;
    }
    return res;
}
};

在这里插入图片描述

写法

vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
    vector<int> res(nums.size(), 0);
    vector<int> sort_vec = nums;
    std::sort(sort_vec.begin(), sort_vec.end());
    int curr, index;
    for (int i = 0; i < nums.size(); ++i) {
        curr = nums[i];
        index = 0;
        for (int j = 0; j < sort_vec.size(); ++j) {
            if (sort_vec[j] >= curr){
                break;
            }
            index++;
        }
        res[i] = index;
    }
    return res;
}

在这里插入图片描述

java

/*    *//*
    * 思路： 复制一份原数组并进行排序， 得到一个临时数据
    *       循环临时数据， 用一个map记录下各个数据的索引位置。
    *
    *       循环原始元素，获取map中对应的索引值，返回即可
    * 比如 [8,1,2,2,3]
    * */
    public static int[] soloution2(int []nums){
        int[] temp = Arrays.copyOf(nums, nums.length);
        Arrays.sort(temp);
        Map<Integer, Integer> mapIndex = new HashMap<>();
        for(int i = 0; i < temp.length; i++){
            if (!mapIndex.containsKey(temp[i])){
                mapIndex.put(temp[i], i);
            }
        }
        int[] res = new int[nums.length];
        for (int i = 0; i < nums.length; i++){
            res[i] = mapIndex.get(nums[i]);
        }
        return res;
    }

解答3：计数排序[最快]

数组中的元素取值为[0,100]，使用频次数组加前缀和的解法

cpp

vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
    vector<int> hash(101, 0);
    for(int iter : nums){
        hash[iter]++;
    }
    vector<int> freq(101, 0);
    freq[0] = 0;
    freq[1] = freq[0];
    for (int j = 2; j < 101; ++j) {
        freq[j] = freq[j - 1] + hash[j - 1];
    }
    vector<int> res(nums.size());
    for (int i = 0; i < nums.size(); ++i) {
        res[i] = freq[nums[i]];
    }
    return res;
}

java

public static int[] smallerNumbersThanCurrent(int[] nums){
        //频次数组---- 每个数字出现多少次
        int[] hash = new int[101];
        for (int num : nums) {
            hash[num]++;
        }
        // 数组中的元素取值为[0,100]
        // 统计比i小的元素的个数
        int[] freq = new int[101];
        freq[0] = 0;
        freq[1] = hash[0];
        for (int i = 2; i < hash.length; i++) {
            freq[i] = freq[i-1] + hash[i - 1];
        }
        // 此时： hash数组中， 值是比索引小的元素个数
        // 循环原数组
        int[] res = new int[nums.length];
        for (int i = 0 ; i < nums.length; i++){
            res[i] = freq[nums[i]];
        }
        return res;
    }