6324. Maximize the great value of the array

topic：

6324. Maximize the great value of the array.md
Give you a bidding 0 Started integer array nums 。You need to nums Re -arrange into a new array perm 。

definition nums of Great value To satisfy 0 <= i < nums.length and perm[i] > nums[i] of下标数目。

Please return to re -arrangement nums 后of maximum Great value。

Exemplary example 1：

enter：nums = [1,3,5,2,1,3,1]
Output：4
explain：A optimal arrangement scheme is perm = [2,5,1,3,3,1,1] 。
The bidding is 0, 1, 3 and 4 Place，All perm[i] > nums[i] 。So we return 4 。

Thought：

Three ways to think about this question：
The first is Tian Ji horse racing（I am）： InumsContinuously reappear，Advance numbers，Then compare（time out）
Then there is a double pointer-Hash table：
每个元素只能被bigof元素指向一次（for example5Compare3big，3Can’t follow4对Compare了）
Two pointers point to the tail element at the same time，whenleft not less than rightof时候，left–。
else left– right– Counter– count ++
Last returncount
灵神ofTian Ji horse racing：
sort后直接在原数组上面找Comparewhen前元素bigof元素

Code：

I am

class Solution:
    def maximizeGreatness(self, nums: List[int]) -> int:
        nums.sort()
        nums_source.sort()
        max_count = 0
        
        # when新数组与旧数组相同时，Stop loop
        for _ in range(len(nums)):
             nums_source = nums_source[1:] + [nums_source[0]]
             print(nums_source, nums)
             count = 0
             for i in range(len(nums)):
                 if nums_source[i] > nums[i]:
                     count += 1
                     print(count)
             max_count = max(max_count, count)
        return max_count

Double pointer+Hash table

class Solution:
    def maximizeGreatness(self, nums: List[int]) -> int:
        nums.sort()
        #print(nums)
        left = len(nums) - 1
        dicts = Counter(nums)
        count = 0
        right = left
        while right >= left >= 0:
            if nums[right] <= nums[left]:
                left -= 1
            if nums[right] > nums[left]:
                if dicts[nums[left]] > 0:
                    dicts[nums[left]] -= 1
                    left -= 1
                    right -= 1
                    count += 1
                    #print(dicts, nums, count)
                else:
                    left -= 1
            elif right == 0 or left == 0:
                break

        return count

Tian Ji horse racing

class Solution:
    def maximizeGreatness(self, nums: List[int]) -> int:
        nums.sort()
        i = 0
        for x in nums:
            if x > nums[i]:
                i += 1
        return i