从零开始刷力扣——数组的改变、移动

前言

这些题目来自于leetcode上发布的一篇讨论有没有人一起从零开始刷力扣与官方推出的力扣刷题攻略，这两篇题单大同小异，都是我认为不错的leetcode入门题单。

本文旨在记录自己的刷题历程，希望早日将这些刷透，烂熟于心。

453.Minimum Moves to Equal Array Elements 最小操作次数使数组元素相等

原题链接：

https://leetcode.cn/problems/minimum-moves-to-equal-array-elements/description/

题目描述：

给你一个长度为 n 的整数数组，每次操作将会使 n - 1 个元素增加 1 。返回让数组所有元素相等的最小操作次数。

方法一：求和 - n * 最小值

要使数组中的所有元素相等，我们需要将所有元素增加到数组中的最大元素值。假设数组中的最大值为 max_val，则将所有元素增加到 max_val 的操作次数为 sum(array) - n * min_val，其中 sum(array) 是数组中所有元素的和，min_val 是数组中的最小值。

算法如下：

找到数组中的最小值 min_val 与数组的总和 sum(array)
计算操作次数为 sum(array) - n * min_val

代码实现：

class Solution:
    def minMoves(self, nums: List[int]) -> int:
        min_val = min(nums)
        total_sum = sum(nums)
        n = len(nums)
        return total_sum - n * min_val

时间复杂度：$O(n)$（仅遍历一次数组）
空间复杂度：$O(1)$

665.Non-decreasing Array 非递减数列

原题链接：

https://leetcode.cn/problems/non-decreasing-array/description/

题目描述：

给你一个长度为 n 的整数数组 nums ，请你判断在最多改变 1 个元素的情况下，该数组能否变成一个非递减数列。

我们是这样定义一个非递减数列的：对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。

方法一：遍历数组

为了判断在最多改变一个元素的情况下，数组能否变成非递减数列，我们可以遍历数组，当遇到 nums[i] > nums[i + 1] 时，则需要进行修正。

如果 nums[i] > nums[i + 1]，有两种修正方案：

将 nums[i] 变为 nums[i + 1]。这样可能会影响前面的数，但不会影响后面的数。
将 nums[i + 1] 变为 nums[i]。这样可能会影响后面的数，但不会影响前面的数。

我们可以尝试第一种方案，如果修正后仍然满足非递减数列的条件，就返回 True；否则，尝试第二种方案，如果修正后仍然满足条件，也返回 True。如果两种方案都不满足条件，就返回 False。

代码实现：

class Solution:
    def checkPossibility(self, nums: List[int]) -> bool:
        modified = False
        n = len(nums)
        
        for i in range(n - 1):
            if nums[i] > nums[i + 1]:
                if modified:
                    return False
                
                if i == 0 or nums[i - 1] <= nums[i + 1]:
                    nums[i] = nums[i + 1]
                else:
                    nums[i + 1] = nums[i]
                    
                modified = True
        
        return True

时间复杂度：$O(n)$

空间复杂度：$O(1)$

283.Move Zeroes 移动零

原题链接：

https://leetcode.cn/problems/move-zeroes/description/

题目描述：

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

方法一：双指针法

可以使用双指针法来实现原地移动数组中的零元素。具体步骤如下：

使用两个指针 left 和 right，初始时都指向数组的开头。
遍历数组，当遇到非零元素时，将其移动到指针 left 所指向的位置，并将 left 指针向后移动一位。
当遍历完成后，left 指针之前的位置都是非零元素，而 left 指针之后的位置都是零元素。
将 left 指针之后的所有元素都置为零即可。

代码实现：

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        left = 0
    
        for right in range(len(nums)):
            if nums[right] != 0:
                nums[left] = nums[right]
                left += 1
        
        for i in range(left, len(nums)):
            nums[i] = 0

时间复杂度：$O(n)$

空间复杂度：$O(1)$