312 lines
9.3 KiB
Markdown
Executable File
312 lines
9.3 KiB
Markdown
Executable File
* [做项目（多个C++、Java、Go、测开、前端项目）](https://www.programmercarl.com/other/kstar.html)
|
||
* [刷算法（两个月高强度学算法）](https://www.programmercarl.com/xunlian/xunlianying.html)
|
||
* [背八股（40天挑战高频面试题）](https://www.programmercarl.com/xunlian/bagu.html)
|
||
|
||
|
||
|
||
# 1365.有多少小于当前数字的数字
|
||
|
||
[力扣题目链接](https://leetcode.cn/problems/how-many-numbers-are-smaller-than-the-current-number/)
|
||
|
||
给你一个数组 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里存放的就是相同元素最左面的数值和下标了**。
|
||
代码如下：
|
||
|
||
```CPP
|
||
int hash[101];
|
||
for (int i = vec.size() - 1; i >= 0; i--) { // 从后向前，记录 vec[i] 对应的下标
|
||
hash[vec[i]] = i;
|
||
}
|
||
```
|
||
|
||
最后在遍历原数组nums，用hash快速找到每一个数值 对应的 小于这个数值的个数。存放在将结果存放在另一个数组中。
|
||
|
||
代码如下：
|
||
|
||
```CPP
|
||
// 此时hash里保存的每一个元素数值 对应的 小于这个数值的个数
|
||
for (int i = 0; i < nums.size(); i++) {
|
||
vec[i] = hash[nums[i]];
|
||
}
|
||
```
|
||
|
||
流程如图：
|
||
|
||
<img src='https://file1.kamacoder.com/i/algo/1365.有多少小于当前数字的数字.png' width=600> </img></div>
|
||
|
||
关键地方讲完了，整体C++代码如下：
|
||
|
||
```CPP
|
||
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：
|
||
|
||
```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：
|
||
|
||
> 暴力法：
|
||
|
||
```python3
|
||
class Solution:
|
||
def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
|
||
res = [0 for _ in range(len(nums))]
|
||
for i in range(len(nums)):
|
||
cnt = 0
|
||
for j in range(len(nums)):
|
||
if j == i:
|
||
continue
|
||
if nums[i] > nums[j]:
|
||
cnt += 1
|
||
res[i] = cnt
|
||
return res
|
||
```
|
||
|
||
> 排序+hash：
|
||
|
||
```python3
|
||
class Solution:
|
||
# 方法一：使用字典
|
||
def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
|
||
res = nums[:]
|
||
hash_dict = dict()
|
||
res.sort() # 从小到大排序之后，元素下标就是小于当前数字的数字
|
||
for i, num in enumerate(res):
|
||
if num not in hash_dict.keys(): # 遇到了相同的数字，那么不需要更新该 number 的情况
|
||
hash_dict[num] = i
|
||
for i, num in enumerate(nums):
|
||
res[i] = hash_dict[num]
|
||
return res
|
||
|
||
# 方法二：使用数组
|
||
def smallerNumbersThanCurrent(self, nums: List[int]) -> List[int]:
|
||
# 同步进行排序和创建新数组的操作，这样可以减少一次冗余的数组复制操作，以减少一次O(n) 的复制时间开销
|
||
sort_nums = sorted(nums)
|
||
# 题意中 0 <= nums[i] <= 100，故range的参数设为101
|
||
hash_lst = [0 for _ in range(101)]
|
||
# 从后向前遍历，这样hash里存放的就是相同元素最左面的数值和下标了
|
||
for i in range(len(sort_nums)-1,-1,-1):
|
||
hash_lst[sort_nums[i]] = i
|
||
for i in range(len(nums)):
|
||
nums[i] = hash_lst[nums[i]]
|
||
return nums
|
||
```
|
||
|
||
### Go：
|
||
|
||
```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：
|
||
|
||
```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：
|
||
|
||
> 暴力法：
|
||
|
||
```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：
|
||
|
||
```typescript
|
||
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;
|
||
};
|
||
```
|
||
|
||
### Rust：
|
||
```rust
|
||
use std::collections::HashMap;
|
||
impl Solution {
|
||
pub fn smaller_numbers_than_current(nums: Vec<i32>) -> Vec<i32> {
|
||
let mut v = nums.clone();
|
||
v.sort();
|
||
let mut hash = HashMap::new();
|
||
for i in 0..v.len() {
|
||
// rust中使用or_insert插入值, 如果存在就不插入,可以使用正序遍历
|
||
hash.entry(v[i]).or_insert(i as i32);
|
||
}
|
||
nums.into_iter().map(|x| *hash.get(&x).unwrap()).collect()
|
||
}
|
||
}
|
||
```
|
||
|
||
|