文章目录

• 1.1365有多少小于当前数字的数字
• • 1.1.题目
  • 1.2.解答
• 2.941有效的山脉数组
• • 2.1.题目
  • 2.2.解答
• 3.1207独一无二的出现次数
• • 3.1.题目
  • 3.2.解答

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

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

1.1.题目

1.2.解答

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

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

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

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

• 用一个哈希表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;
}

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

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

最后给出整体代码如下：

vector smallerNumbersThanCurrent(vector &nums)
{// 1.对数组元素进行排序，则排序后的索引就是比他小的数组的元素个数vector 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;
}

2.941有效的山脉数组

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

2.1.题目

2.2.解答

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

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

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

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

最后给出代码如下：

bool validMountainArray(vector &arr)
{// 小于三个元素肯定不是山峰，直接返回falseif(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;
}

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 &arr)
{unordered_map umap;  // 存储数字和出现的频率unordered_set fre;  // 存储出现的频率// 1.统计数字出现的频率for(const auto& num : arr){if(umap.find(num) == umap.end())umap.insert({num, 0});elseumap[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);  // 如果没有则插入这个新的频率}      // 运行到这里说明没有重复的频率，返回truereturn true;  
}