leetcode-每日一题-No.3151. 特殊数组 I

题目

如果数组的每一对相邻元素都是两个奇偶性不同的数字，则该数组被认为是一个 特殊数组 。

Aging 有一个整数数组 nums。如果 nums 是一个 特殊数组 ，返回 true，否则返回 false。

示例 1：

输入：nums = [1]

输出：true

解释：

只有一个元素，所以答案为 true。

示例 2：

输入：nums = [2,1,4]

输出：true

解释：

只有两对相邻元素： (2,1) 和 (1,4)，它们都包含了奇偶性不同的数字，因此答案为 true。

示例 3：

输入：nums = [4,3,1,6]

输出：false

解释：

nums[1] 和 nums[2] 都是奇数。因此答案为 false。

提示：

• 1 <= nums.length <= 100

• 1 <= nums[i] <= 100

答案代码

class Solution(object):
    def isArraySpecial(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        # O(n)初级写法
        """
        if not nums:
            return True
        for i in range(len(nums) - 1):
            if (nums[i] % 2) == (nums[i + 1] % 2):
                return False
        return True
        """
        # O(n)高级写法
        # 检查相邻元素的奇偶性是否不同
        return all((nums[i] % 2) != (nums[i + 1] % 2) for i in range(len(nums) - 1))


if __name__ == '__main__':
    print(Solution().isArraySpecial([1]))  # True
    print(Solution().isArraySpecial([2, 1, 4]))  # True
    print(Solution().isArraySpecial([4, 3, 1, 6]))  # False
    print(Solution().isArraySpecial([2, 4, 6]))  # False

答案分析

思路

暴力解法

解题过程

直接遍历：我们遍历了整个数组，每次检查一对相邻元素。这是一种典型的暴力解法，因为它没有使用任何优化技巧或数据结构来减少遍历的次数或提前剪枝。

在当前问题中，暴力解法已经是最优的时间复杂度，因为要验证数组的所有相邻元素对，必须遍历整个数组。除非有其他关于输入数据的特殊性质，否则不可能在一般情况下进一步优化时间复杂度。

复杂度

时间复杂度分析：

1. if not nums: 语句：这是一个常数时间操作，复杂度为 O(1)。

2. for i in range(len(nums) - 1): 循环：这个循环遍历了 nums 列表中的所有元素（除了最后一个），所以循环的执行次数是 len(nums) - 1。在最坏的情况下，循环内的条件判断语句 if (nums[i] % 2) == (nums[i + 1] % 2): 也会执行 len(nums) - 1 次。每次判断都是常数时间操作，因此整个循环的时间复杂度是 O(n)，其中 n 是列表 nums 的长度。

综上所述，整个函数的时间复杂度为 O(n)。

空间复杂度分析：

1. 常数空间：代码中没有使用额外的空间，只有少量的额外变量（如循环变量 i 和函数返回值），这些都是常数空间。

因此，函数的空间复杂度为 O(1)。

总结：

• 时间复杂度：O(n)

• 空间复杂度：O(1)