代码随想录61——额外题目【数组】：1365有多少小于当前数字的数字、941有效的山脉数组、1207独一无二的出现次数

1.1365有多少小于当前数字的数字

参考：代码随想录，1365有多少小于当前数字的数字；力扣题目链接

1.1.题目

1.2.解答

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

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

• 首先要找小于当前数字的数字，那么从小到大排序之后，该数字之前的数字就都是比它小的了。所以可以定义一个新数组，将数组排个序。排序之后，其实每一个数值的下标就代表这前面有几个比它小的了。

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

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

• 此时有一个情况，就是数值相同怎么办？

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

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

注意：其实就是说，在存在相同数字的时候，只有最左边的数字的索引才等于小于它的元素的个数，所以在对排序后的数组进行从后向前遍历、用hash记录的时候，相同的数字在hash表中的值一值再被复写，直到最后一次遍历到相同数字的最左边的数字，此时进行最后一次复写，留下来的也就是正确的答案。

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

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

// 此时hash里保存的每一个元素数值 对应的 小于这个数值的个数
for (int i = 0; i < nums.size(); i++) {
    vec[i] = hash[nums[i]];  // 注意这里可以复用前面的vec，这样节省空间
1
2
3

最后给出整体代码如下：

vector<int> smallerNumbersThanCurrent(vector<int> &nums)
{
    // 1.对数组元素进行排序，则排序后的索引就是比他小的数组的元素个数
    vector<int> vec = nums;   // 注意要复制数组，否则会打乱数组的原有顺序
    sort(vec.begin(), vec.end());

    // 2.定义哈希数组并填充
    int hash[101] = {0};   // 题目说了 0 <= nums[i] <= 100，也就是hash表的值都在这些数中间
    // 填充哈希数组：从后往前填充，这样保证相同数字其索引都是左边数字的索引，才等于把它小的元素个数
    for(int i = vec.size()-1; i >=0; i--)
        hash[vec[i]] = i;   // 键是数值，值是索引
    
    // 3.遍历原数组，根据元素的值到哈希表中寻找对应的索引，就是数组中值比他小的元素个数
    for(int i = 0; i < nums.size(); i++)
    {
        vec[i] = hash[nums[i]];   // 这里复用vec数组来存储最终结果，节省空间
    }

    return vec;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.941有效的山脉数组

参考：代码随想录，941有效的山脉数组；力扣题目链接

2.1.题目

2.2.解答

判断是山峰，主要就是要严格的保证左边到中间，和右边到中间是递增的。

这样可以使用两个指针，left和right，让其按照如下规则移动，如图：

注意这里还是有一些细节，例如如下两点：

• 因为left和right是数组下标，移动的过程中注意不要数组越界
• 如果left或者right没有移动，说明是一个单调递增或者递减的数组，依然不是山峰

最后给出代码如下：

bool validMountainArray(vector<int> &arr)
{
    // 小于三个元素肯定不是山峰，直接返回false
    if(arr.size() < 3)
        return false;
    
    // 左右指针
    int left = 0;
    int right = arr.size() - 1;

    // 左指针按照升序一直右移，右指阵按照降序一致左移
    while(left < arr.size()-1 && arr[left] < arr[left+1])
        left++;
    while(right > 0 && arr[right-1] > arr[right])
        right--;
    
    // 最后判断结果：左右指针相遇，并且都不是在起点（也就是都进行了移动）
    if(left == right && left != 0 && right != arr.size()-1)
        return true;
    
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3.1207独一无二的出现次数

参考：代码随想录，1207独一无二的出现次数；力扣题目链接

3.1.题目

3.2.解答

这道题目其实思路很简单：

• 先用unordered_map统计每个数字出现的次数，也就是频率
• 然后遍历频率值，只用unordered_set几率已经出现过的频率，看是否有重复的频率。如果有重复的频率直接返回false；如果遍历完所有频率没有重复的，则返回true。

代码随想录上根据数据的范围使用数组来实现unordered_map和unodered_set的功能，实际上直接使用unordered_map和unordered_set即可， 因为他们修改和查找的时间复杂度都是O(1)。

最后给出使用unordered_map和unordered_set实现的代码：

bool uniqueOccurrences(vector<int> &arr)
{
    unordered_map<int, int> umap;  // 存储数字和出现的频率
    unordered_set<int> fre;  // 存储出现的频率

    // 1.统计数字出现的频率
    for(const auto& num : arr)
    {
        if(umap.find(num) == umap.end())
            umap.insert({num, 0});
        else
            umap[num]++;
    }

    // 2.遍历umap，看其中的值是否有重复的
    auto it = umap.begin();
    for(; it != umap.end(); it++)
    {
        if(fre.find(it->second) != fre.end())   // 如果有出现的频率，直接返回
            return false;
        fre.insert(it->second);  // 如果没有则插入这个新的频率
    }      

    // 运行到这里说明没有重复的频率，返回true
    return true;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26