【Python 算法零基础 1.线性枚举】

我装作漠视一切，以为这样就可以不在乎

                                                        —— 25.3.17

一、线性枚举的基本概念

1.时间复杂度

        线性枚举的时间复杂度为 O(nm)，其中 n是线性表的长度。m 是每次操作的量级，对于求最大值和求和来说，因为操作比较简单，所以 m为 1，则整体的时间复杂度是 O(n)的。这是因为线性枚举需要遍历列表中的每个元素。在处理大规模数据时，可能需要使用更高效的算法来提高搜索速度。

2.优化算法

二分查找：如果线性表已经排序，可以使用二分搜索来提高搜索效率。

哈希表：可以使用哈希表来存储已经搜索过的元素，避免重复搜索。

前缀和：可以存储前 i 个元素的和，避免重复计算。

双指针：可以从两头开始搜索，提升搜索效率。

---

二、实战

1.1550. 存在连续三个奇数的数组

给你一个整数数组 arr，请你判断数组中是否存在连续三个元素都是奇数的情况：如果存在，请返回 true ；否则，返回 false 。

示例 1：

输入：arr = [2,6,4,1]
输出：false
解释：不存在连续三个元素都是奇数的情况。

示例 2：

输入：arr = [1,2,34,3,4,5,7,23,12]
输出：true
解释：存在连续三个元素都是奇数的情况，即 [5,7,23] 。

提示：

• 1 <= arr.length <= 1000
• 1 <= arr[i] <= 1000

方法一 线性枚举

思路与算法

​遍历数组：代码通过一个 for 循环遍历数组 arr，从第二个元素开始，到倒数第二个元素结束。这样做的目的是为了确保在检查 arr[i-1]、arr[i] 和 arr[i+1] 时不会越界。

检查连续奇数：在每次循环中，代码检查当前元素 arr[i] 及其前一个元素 arr[i-1] 和后一个元素 arr[i+1] 是否都是奇数。这是通过取模运算 % 2 == 1 来判断的。如果这三个元素都是奇数，则说明存在三个连续的奇数，函数立即返回 True。​

返回结果：如果遍历完整个数组都没有找到三个连续的奇数，则函数返回 False。

class Solution:def threeConsecutiveOdds(self, arr: List[int]) -> bool:n = len(arr)for i in range(1, n - 1):if arr[i - 1] % 2 == 1 and arr[i] % 2 == 1 and arr[i+1] % 2 == 1:return Truereturn False

---

2.485. 最大连续 1 的个数

给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。

示例 1：

输入：nums = [1,1,0,1,1,1]
输出：3
解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.

示例 2:

输入：nums = [1,0,1,1,0,1]
输出：2

提示：

• 1 <= nums.length <= 105
• nums[i] 不是 0 就是 1.

方法一 线性枚举

思路与算法

​初始化变量：sumNum：用于记录当前连续 1 的个数。maxNum：用于记录遍历过程中找到的最长连续 1 的个数。

遍历数组：使用一个 for 循环遍历数组 nums 的每一个元素。如果当前元素是 0，说明连续的 1 中断了，将 sumNum 重置为 0。如果当前元素是 1，将 sumNum 加 1，表示当前连续 1 的个数增加了。更新最大值：在每次循环中，用 maxNum 记录当前找到的最长连续 1 的个数，通过 max(maxNum, sumNum) 实现。​

返回结果：遍历结束后，maxNum 就是整个数组中最长的连续 1 的个数，将其返回。

class Solution:def findMaxConsecutiveOnes(self, nums: List[int]) -> int:n = len(nums)sumNum = 0maxNum = 0for i in range(n):if nums[i] == 0:sumNum = 0else:sumNum += 1maxNum = max(maxNum, sumNum)return maxNum

---

3.540. 有序数组中的单一元素

给你一个仅由整数组成的有序数组，其中每个元素都会出现两次，唯有一个数只会出现一次。

请你找出并返回只出现一次的那个数。

你设计的解决方案必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度。

示例 1:

输入: nums = [1,1,2,3,3,4,4,8,8]
输出: 2

示例 2:

输入: nums =  [3,3,7,7,10,11,11]
输出: 10

提示:

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 105

方法一 线性枚举

思路与算法

​特殊情况处理：如果数组长度为 1，直接返回唯一的元素 nums[0]，因为它一定是不重复的。​

遍历数组：使用一个 for 循环遍历数组 nums，从第二个元素开始，到倒数第二个元素结束（避免越界）。对于当前元素 nums[i]，检查它是否与前后元素都不相等：如果 nums[i] != nums[i - 1] 且 nums[i] != nums[i + 1]，则 nums[i] 就是唯一不重复的元素，直接返回。

边界情况处理：如果遍历结束后没有找到不重复的元素，说明不重复的元素可能在数组的边界：检查第一个元素 nums[0] 是否与第二个元素 nums[1] 不相等，如果是，则返回 nums[0]。否则，返回最后一个元素 nums[n - 1]。

class Solution:def singleNonDuplicate(self, nums: List[int]) -> int:n = len(nums)if n == 1:return nums[0]for i in range(1, n - 1):if nums[i] != nums[i - 1] and nums[i] != nums[i + 1]:return nums[i]if nums[0] != nums[1]:return nums[0]return nums[n - 1]

---

方法二 二分查找

题目要求设计出的算法必须满足 O(log n) 时间复杂度和 O(1) 空间复杂度

思路与算法

初始化指针：定义两个指针 l 和 r，分别指向数组的起始位置和结束位置。

二分查找：在 while 循环中，计算中间位置 mid = (l + r) // 2。

利用 mid ^ 1 来检查 nums[mid] 是否与它的配对元素相等：如果 mid 是偶数，mid ^ 1 就是 mid + 1。如果 mid 是奇数，mid ^ 1 就是 mid - 1。如果 nums[mid] != nums[mid ^ 1]，说明不重复元素在 mid 的左侧，将 r 更新为 mid。否则，说明不重复元素在 mid 的右侧，将 l 更新为 mid + 1。

​返回结果：当 l == r 时，循环结束，nums[l] 就是唯一不重复的元素。

^ 是 ​按位异或（Bitwise XOR）​ 运算符。它的作用是对两个整数的二进制表示逐位进行异或运算，并返回结果。 

对于两个二进制位：

• 如果两个位相同（都是 0 或都是 1），结果为 0。
• 如果两个位不同（一个是 0，另一个是 1），结果为 1。

class Solution:def singleNonDuplicate(self, nums: List[int]) -> int:n = len(nums)l, r = 0, n - 1while l < r:mid = (l + r) // 2if nums[mid] != nums[mid ^ 1]:r = midelse:l = mid + 1return nums[l]