好看的wordpress文章模板,上海seo优化推广,怎么开发自己的网站,财经大学网站建设1、题目
给你一个数组 nums#xff0c;对于其中每个元素 nums[i]#xff0c;请你统计数组中比它小的所有数字的数目。
换而言之#xff0c;对于每个 nums[i] 你必须计算出有效的 j 的数量#xff0c;其中 j 满足 j ! i 且 nums[j] nums[i] 。
以数组形式返回答案。…1、题目
给你一个数组 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 存在四个比它小的数字122 和 3。 对于 nums[1]1 不存在比它小的数字。 对于 nums[2]2 存在一个比它小的数字1。 对于 nums[3]2 存在一个比它小的数字1。 对于 nums[4]3 存在三个比它小的数字12 和 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
2、解
暴力解 vectorint smallerNumberThanCurrent(vectorint nums){vectorint copy nums;nums.clear();unordered_mapint, int numTimes;for(auto num : copy){numTimes[num];}for(auto n : copy){int temp 0;for(auto [num, times] : numTimes){if(num n) temp times;}nums.push_back(temp);}return nums;}另解 先从小到大排序排序之后每个数值的下标就代表着前面有几个比它小的数字再通过一个哈希表这里数组也可来做数值和下标的映射这样就可以通过数值快速知道下标。
对于相同数值的元素在构造数组hash的时候从后向前遍历这样hash里存放的就是相同元素最左面的数值和下标了。 比如数组1 2 3 4 4 4 如果从前往后遍历第一个数值4的下标是3第二个数值4的下标是4了而从后往前遍历数值4的下标最终将会是最左边的下标3。
最后再遍历原数组nums用hash快速找到每一个数值 对应的 小于这个数值的个数。存放在将结果存放在另一个数组中。 vectorint smallerNumberThanCurrentA(vectorint nums){int hash[101];vectorint result nums;sort(result.begin(), result.end());for(int i result.size() - 1; i 0; i--){hash[result[i]] i;}for(int i 0; i nums.size(); i){result[i] hash[nums[i]];}return result;}
