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

╰半橙微兮° 2023-07-25 09:44 58阅读 0赞

# 题目来源 #

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

# 题目描述 #

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_10_color_FFFFFF_t_70_g_se_x_16]

# 题目解答 #

## 暴力循环法 ##

### 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;
    }

![在这里插入图片描述][5bf3fba188e647eea5baefaa7c95cc95.png]

### 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;
    }
    };

![在这里插入图片描述][79ec3d1bf1fe48c88193fd8f5d38ce1e.png]

#### 写法 ####

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;
    }

![在这里插入图片描述][3b3459e06de048fe87a37ad3df3d7767.png]

### 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;
        }

[1365.]: https://leetcode-cn.com/problems/how-many-numbers-are-smaller-than-the-current-number/
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20230528/ad156d9a0e5a4200881037b023a48a33.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBAT2NlYW4mJlN0YXI_size_10_color_FFFFFF_t_70_g_se_x_16]: /images/20230528/6935622939d2479c9a1d7c0e35d858dc.png
[5bf3fba188e647eea5baefaa7c95cc95.png]: /images/20230528/c9731eeffa674d02a77760cca7a3db4d.png
[79ec3d1bf1fe48c88193fd8f5d38ce1e.png]: /images/20230528/8bc8dc32199443fd9d05fa14ea25adcd.png
[3b3459e06de048fe87a37ad3df3d7767.png]: /images/20230528/8106862a9ee449118b088b4aa62920ad.png