题目:
6324. 最大化数组的伟大值.md
给你一个下标从 0 开始的整数数组 nums 。你需要将 nums 重新排列成一个新的数组 perm 。
定义 nums 的 伟大值 为满足 0 <= i < nums.length 且 perm[i] > nums[i] 的下标数目。
请你返回重新排列 nums 后的 最大 伟大值。
示例 1:
输入:nums = [1,3,5,2,1,3,1]
输出:4
解释:一个最优安排方案为 perm = [2,5,1,3,3,1,1] 。
在下标为 0, 1, 3 和 4 处,都有 perm[i] > nums[i] 。因此我们返回 4 。
思想:
这道题想了三种方法:
首先是田忌赛马(我流): 我把nums不断地重排,把数字提前,然后对比(超时)
然后是双指针-哈希表:
每个元素只能被大的元素指向一次(比如5比3大,3就不能再跟4对比了)
两个指针同时指向尾元素,当left 不小于 right的时候,left–。
else left– right– Counter– count ++
最后返回count
灵神的田忌赛马:
sort后直接在原数组上面找比当前元素大的元素
代码:
1 | class Solution: |
1 | class Solution: |
1 | class Solution: |