Skip to content

Latest commit

 

History

History
268 lines (212 loc) · 7.87 KB

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

File metadata and controls

268 lines (212 loc) · 7.87 KB

参与本项目,贡献其他语言版本的代码,拥抱开源,让更多学习算法的小伙伴们收益!

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

力扣题目链接

给你一个数组 nums,对于其中每个元素 nums[i],请你统计数组中比它小的所有数字的数目。

换而言之,对于每个 nums[i] 你必须计算出有效的 j 的数量,其中 j 满足 j != i 且 nums[j] < nums[i] 。

以数组形式返回答案。

示例 1:

  • 输入:nums = [8,1,2,2,3]
  • 输出:[4,0,1,1,3]
  • 解释: 对于 nums[0]=8 存在四个比它小的数字:(1,2,2 和 3)。
    对于 nums[1]=1 不存在比它小的数字。
    对于 nums[2]=2 存在一个比它小的数字:(1)。
    对于 nums[3]=2 存在一个比它小的数字:(1)。
    对于 nums[4]=3 存在三个比它小的数字:(1,2 和 2)。

示例 2:

  • 输入:nums = [6,5,4,8]
  • 输出:[2,1,0,3]

示例 3:

  • 输入:nums = [7,7,7,7]
  • 输出:[0,0,0,0]

提示:

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

思路

两层for循环暴力查找,时间复杂度明显为$O(n^2)$。

那么我们来看一下如何优化。

首先要找小于当前数字的数字,那么从小到大排序之后,该数字之前的数字就都是比它小的了。

所以可以定义一个新数组,将数组排个序。

排序之后,其实每一个数值的下标就代表这前面有几个比它小的了

代码如下:

vector<int> vec = nums;
sort(vec.begin(), vec.end()); // 从小到大排序之后,元素下标就是小于当前数字的数字

用一个哈希表hash(本题可以就用一个数组)来做数值和下标的映射。这样就可以通过数值快速知道下标(也就是前面有几个比它小的)。

此时有一个情况,就是数值相同怎么办?

例如,数组:1 2 3 4 4 4 ,第一个数值4的下标是3,第二个数值4的下标是4了。

这里就需要一个技巧了,在构造数组hash的时候,从后向前遍历,这样hash里存放的就是相同元素最左面的数值和下标了。 代码如下:

int hash[101];
for (int i = vec.size() - 1; i >= 0; i--) { // 从后向前,记录 vec[i] 对应的下标
    hash[vec[i]] = i;
}

最后在遍历原数组nums,用hash快速找到每一个数值 对应的 小于这个数值的个数。存放在将结果存放在另一个数组中。

代码如下:

// 此时hash里保存的每一个元素数值 对应的 小于这个数值的个数
for (int i = 0; i < nums.size(); i++) {
    vec[i] = hash[nums[i]];
}

流程如图:

关键地方讲完了,整体C++代码如下:

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> vec = nums;
        sort(vec.begin(), vec.end()); // 从小到大排序之后,元素下标就是小于当前数字的数字
        int hash[101];
        for (int i = vec.size() - 1; i >= 0; i--) { // 从后向前,记录 vec[i] 对应的下标
            hash[vec[i]] = i;
        }
        // 此时hash里保存的每一个元素数值 对应的 小于这个数值的个数
        for (int i = 0; i < nums.size(); i++) {
            vec[i] = hash[nums[i]];
        }
        return vec;
    }
};

可以排序之后加哈希,时间复杂度为$O(n\log n)$

其他语言版本

Java:

public int[] smallerNumbersThanCurrent(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>(); // 记录数字 nums[i] 有多少个比它小的数字
        int[] res = Arrays.copyOf(nums, nums.length);
        Arrays.sort(res);
        for (int i = 0; i < res.length; i++) {
            if (!map.containsKey(res[i])) { // 遇到了相同的数字,那么不需要更新该 number 的情况
                map.put(res[i], i);
            }
        }

        for (int i = 0; i < nums.length; i++) {
            res[i] = map.get(nums[i]);
        }

        return res;
    }

Python:

class Solution:
    def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
        res = nums[:]
        hash = dict()
        res.sort() # 从小到大排序之后,元素下标就是小于当前数字的数字
        for i, num in enumerate(res):
            if num  not in hash.keys(): # 遇到了相同的数字,那么不需要更新该 number 的情况
                hash[num] = i       
        for i, num in enumerate(nums):
            res[i] = hash[num]
        return res

Go:

func smallerNumbersThanCurrent(nums []int) []int {
    // map,key[数组中出现的数] value[比这个数小的个数]
    m := make(map[int]int)
    // 拷贝一份原始数组
    rawNums := make([]int,len(nums)) 
    copy(rawNums,nums)
    // 将数组排序
    sort.Ints(nums)
    // 循环遍历排序后的数组,值为map的key,索引为value
    for i,v := range nums {
        _,contains := m[v]
        if !contains {
          m[v] = i
        } 
          
    }
    // 返回值结果
    result := make([]int,len(nums))
    // 根据原始数组的位置,存放对应的比它小的数
    for i,v := range rawNums {
        result[i] = m[v]
    }

    return result
}

JavaScript:

// 方法一:使用哈希表记录位置
var smallerNumbersThanCurrent = function(nums) {
    const map = new Map();// 记录数字 nums[i] 有多少个比它小的数字
    const res = nums.slice(0);//深拷贝nums
    res.sort((a,b) => a - b);
    for(let i = 0; i < res.length; i++){
        if(!map.has(res[i])){// 遇到了相同的数字,那么不需要更新该 number 的情况
            map.set(res[i],i);
        }
    }
    // 此时map里保存的每一个元素数值 对应的 小于这个数值的个数
    for(let i = 0; i < nums.length; i++){
        res[i] = map.get(nums[i]);
    }
    return res;
};

// 方法二:不使用哈希表,只使用一个额外数组
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var smallerNumbersThanCurrent = function(nums) {
    let array = [...nums];   // 深拷贝
    // 升序排列,此时数组元素下标即是比他小的元素的个数
    array = array.sort((a, b) => a-b);
    let res = [];
    nums.forEach( x => {
        // 即使元素重复也不怕,indexOf 只返回找到的第一个元素的下标
        res.push(array.indexOf(x));
    })
    return res;
};

TypeScript:

暴力法:

function smallerNumbersThanCurrent(nums: number[]): number[] {
    const length: number = nums.length;
    const resArr: number[] = [];
    for (let i = 0; i < length; i++) {
        let count: number = 0;
        for (let j = 0; j < length; j++) {
            if (nums[j] < nums[i]) {
                count++;
            }
        }
        resArr[i] = count;
    }
    return resArr;
};

排序+hash

function smallerNumbersThanCurrent(nums: number[]): number[] {
    const length: number = nums.length;
    const sortedArr: number[] = [...nums];
    sortedArr.sort((a, b) => a - b);
    const hashMap: Map<number, number> = new Map();
    for (let i = length - 1; i >= 0; i--) {
        hashMap.set(sortedArr[i], i);
    }
    const resArr: number[] = [];
    for (let i = 0; i < length; i++) {
        resArr[i] = hashMap.get(nums[i]);
    }
    return resArr;
};