数组类

image.png

#思路，copy原数组，让nums与copy的数组做比较，
class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        nums_copy = sorted(nums)
        res = []
        for i in range(len(nums)):
            if nums_copy[i] == nums[i]:
                continue
            else:
                res.append(i)
        if not res:
            return 0
        return res[-1] - res[0] + 1

#思路：
#从左往右看，因为要得到一个升序，所以右边的数一定要比左边的数大，
#如果不是的话，则说明是需要修改的位置，用right来记录最右边需要修改的位置
#从右往左看，左边的数一定要比右边的数大
#如果不是的话，则说明是需要修改的位置，用left来记录最左边需要修改的位置
class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        left, right = len(nums), 1
        max_num, min_num = nums[0], nums[-1]
        for i in range(len(nums)):
            if nums[i] >= max_num:
                max_num = nums[i]
            else:
                right = i
        for i in range(len(nums) - 1, -1, -1):
            if nums[i] <= min_num:
                min_num = nums[i]
            else:
                left = i
        if right <= left:
            return 0
        return right - left + 1

image.png

#思路：感觉对于这种题都是遍历一次数组，然后和某一个值作比较，作差得到结果
#这道题先排序，然后遍历数组，数组的值小于等于其前一个位置的值，那么让该位置更新为前一个位置的值加1，
#因为每次只能加1，所以操作次数就是改变后的值与未改变的值的差
class Solution:
    def minIncrementForUnique(self, A: List[int]) -> int:
        A.sort()
        res = 0
        for i in range(1,len(A)):
            if A[i] <= A[i-1]:
                res += A[i-1] + 1 - A[i]
                A[i] = A[i-1] +1
            else:
                continue
        return res