【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 <= 10001 <= 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 True
return 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 <= 105nums[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 = 0
maxNum = 0
for i in range(n):
if nums[i] == 0:
sumNum = 0
else:
sumNum += 1
maxNum = 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 <= 1050 <= 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 - 1
while l < r:
mid = (l + r) // 2
if nums[mid] != nums[mid ^ 1]:
r = mid
else:
l = mid + 1
return nums[l]