目录
一、有序数组中的单一元素
1.1思路
1.2 代码实现
1.3 运行结果
二、长度最小的子数组
2.1思路
2.2 代码
2.3 运行结果
三、 山脉数组中查找目标值
3.1 思路
3.2 代码
3.3 运行结果
四、寻找旋转排序数组中的最小值
4.1思路
4.2代码
4.3 运行结果
一、有序数组中的单一元素
力扣第540题
1.1思路
利用二分查找思想：
根据要求在 O(log n) 的时间复杂度和 O(1) 空间复杂度内找出只出现一次的数，因此可以考虑使用二分查找结合异或运算的方法。
而且由于数组中每个元素都会出现两次，唯有一个数只会出现一次，因此在此题中可以使用异或运算。异或运算具有以下性质：
①任何数和 0 进行异或运算，结果仍然是这个数本身。
②任何数和其自身进行异或运算，结果为 0。
基于这个性质，我们可以利用异或运算来找出只出现一次的那个数。
具体步骤如下：
1.初始化左指针 left = 0 和右指针 right = n-1，其中 n 是数组长度。
2.进入循环，直到 left > right：
·计算中间位置 mid = (left + right) // 2。
·如果 mid 是偶数，判断 nums[mid] 是否等于 nums[mid+1]。如果相等，则说明目标元素在 mid 右边，将 left 指针移到 mid+2；否则，目标元素在 mid 左边，将 right 指针移到 mid。
·如果 mid 是奇数，判断 nums[mid] 是否等于 nums[mid-1]。如果相等，则说明目标元素在 mid 右边，将 left 指针移到 mid+1；否则，目标元素在 mid 左边，将 right 指针移到 mid-1。
3.循环结束后，返回 nums[left]。
这样就可以在 O(log n) 的时间复杂度和 O(1) 空间复杂度内找出只出现一次的数。
1.2 代码实现
def singleNonDuplicate(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if mid % 2 == 0:
if nums[mid] == nums[mid+1]:
left = mid + 2
else:
right = mid
else:
if nums[mid] == nums[mid-1]:
left = mid + 1
else:
right = mid - 1
return nums[left]
# 示例测试
print(singleNonDuplicate([1,1,2,2,3,4,4,8,8]))
print(singleNonDuplicate([3,3,7,7,10,10,11])) 1.3 运行结果
代码中的测试的数组：
[1,1,2,2,3,4,4,8,8] 元素3出现一次
[3,3,7,7,10,10,11] 元素11出现一次
二、长度最小的子数组
力扣第209题
2.1思路
为了找到满足总和大于等于 target 的长度最小的连续子数组。
思路：滑动窗口、前缀和、二分查找
具体思路如下：
首先初始化左指针 left、右指针 right 和当前窗口内元素的和 window_sum，初始值均为 0。
进入循环，当右指针小于数组长度时执行以下操作：
将右指针 right 对应元素的值加到 window_sum 中。
如果 window_sum 大于等于目标值 target，进入内部循环：
更新最小长度 min_len，为当前窗口长度与之前的最小长度的较小值。
从当前窗口中减去左指针 left 对应元素的值，并将左指针向右移动一位。
将右指针向右移动一位。
返回最小长度 min_len。
如果不存在满足条件的子数组，则返回0。
2.2 代码
from typing import List
class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] > nums[right]:
left = mid + 1
elif nums[mid] < nums[right]:
right = mid
else:
right -= 1
return nums[left]
if __name__ == "__main__":
solution = Solution()
# 测试示例1
nums_1 = [4, 5, 6, 7, 0, 1, 2]
result_1 = solution.findMin(nums_1)
print(f"The minimum element in {nums_1} is: {result_1}")
# 测试示例2
nums_2 = [3, 4, 5, 1, 2]
result_2 = solution.findMin(nums_2)
print(f"The minimum element in {nums_2} is: {result_2}")
# 测试示例3
nums_3 = [1]
result_3 = solution.findMin(nums_3)
print(f"The minimum element in {nums_3} is: {result_3}")2.3 运行结果
由于在[1,1,1,1,1,1,1,1]中无法得到和为11的连续子数组，返回0
由于篇幅限制，下面两题仅展示运行结果
三、 山脉数组中查找目标值
力扣第1095题
3.1 思路
当给定一个山脉数组 mountainArr 和目标值 target，我们需要找到能使得 mountainArr.get(index) 等于 target 的最小下标 index。
解题思路如下：
首先，我们需要确定山峰的位置。山峰是指数组中的一个最大值，满足 A[i-1] < A[i] > A[i+1] 的条件。我们可以使用二分查找来找到山峰的位置。
定义左指针 left 为数组的起始位置，右指针 right 为数组的结束位置。
进入循环，当 left < right 时进行迭代：
计算中间位置 mid，即 (left + right) // 2。
如果 mountainArr.get(mid) < mountainArr.get(mid+1)，则说明 mid 左侧为上升趋势，右侧可能存在山峰，将 left 移至 mid + 1。
否则，mid 右侧为下降趋势，左侧可能存在山峰，将 right 移至 mid。
循环结束后，left 或 right 即为山峰所在位置，记为 peak。
接下来，我们可以对山峰的左右两侧分别进行二分查找：
使用标准的二分查找方法在 [0, peak] 区间内查找目标值 target。如果找到目标值，直接返回其下标。
如果左侧未找到目标值，则在 [peak+1, n-1] 区间内进行反向二分查找。即令 mountainArr.get(mid) > target 时移动右指针，反之移动左指针。
如果右侧未找到目标值或左侧未找到目标值，则返回 -1。
综上所述，我们可以定义一个辅助函数 binary_search 来实现二分查找。
在编写示例测试部分时，首先进行 MountainArray 类的设计并在其中实现 length() 和 get(index) 方法。这两个方法分别用于获取数组长度和获取指定下标的元素。
3.2 代码
class Solution:
def findInMountainArray(self, target: int, mountainArr: 'MountainArray') -> int:
n = mountainArr.length()
left, right = 0, n - 1
# 二分查找山峰所在的位置
while left < right:
mid = (left + right) // 2
if mountainArr.get(mid) < mountainArr.get(mid+1):
left = mid + 1
else:
right = mid
peak = left # 左右端点重合处即为山峰位置
idx = self.binary_search(mountainArr, 0, peak, target)
if idx != -1:
return idx
return self.binary_search(mountainArr, peak+1, n-1, target)
def binary_search(self, mountainArr, left, right, target):
while left <= right:
mid = (left + right) // 2
cur = mountainArr.get(mid)
if cur == target:
return mid
elif cur < target:
left = mid + 1
else:
right = mid - 1
return -1
class MountainArray:
def __init__(self, arr):
self.arr = arr
def length(self):
return len(self.arr)
def get(self, index):
return self.arr[index]
# 示例测试
if __name__ == "__main__":
# 创建山脉数组实例
mountain_arr_1 = MountainArray([1, 2, 3, 4, 5, 3, 1])
mountain_arr_2 = MountainArray([0, 1, 2, 4, 2, 1, 0])
# 创建解决方案实例
solution = Solution()
# 测试1查找目标值为 3 的下标
target_1 = 3
result_1 = solution.findInMountainArray(target_1, mountain_arr_1)
print(f"[1, 2, 3, 4, 5, 3, 1]测试一（查找3）结果: {result_1}")
# 测试2查找目标值为 5 的下标
target_2 = 5
result_2 = solution.findInMountainArray(target_2, mountain_arr_2)
print(f"[0, 1, 2, 4, 2, 1, 0]测试二（查找5）结果: {result_2}")
3.3 运行结果
测试一中，元素3的下标为2，成功找到并输出了其下标。
测试二中，元素5未在数组中出现，按照题目要求返回了-1
四、寻找旋转排序数组中的最小值
力扣第154题
4.1思路
采用二分查找的方法：
首先定义一个 Solution 类，其中包含一个名为 findMin 的方法，用于找到给定数组中的最小元素。
在 findMin 方法中，定义左右指针 left 和 right，初始值分别为 0 和数组长度减 1，表示当前搜索范围为整个数组。
进入循环，当 left 小于 right 时执行以下步骤：
计算中间元素的索引 mid = (left + right) // 2。
比较 nums[mid] 和 nums[right] 的值：
如果 nums[mid] > nums[right]，说明最小元素在 mid 的右侧，更新 left = mid + 1。
如果 nums[mid] < nums[right]，说明最小元素在 mid 的左侧或者就是 nums[mid]，更新 right = mid。
如果 nums[mid] == nums[right]，无法判断最小元素在哪一侧，因此将 right 减一，缩小搜索范围。
循环结束后，返回 nums[left]（或 nums[right]）作为最小元素。
在 main 函数中，创建 Solution 类的实例，然后进行示例测试，验证代码的正确性。
4.2代码
1.from typing import List
2.
3.class Solution:
4. def findMin(self, nums: List[int]) -> int:
5. left, right = 0, len(nums) - 1
6.
7. while left < right:
8. mid = (left + right) // 2
9.
10. if nums[mid] > nums[right]:
11. left = mid + 1
12. elif nums[mid] < nums[right]:
13. right = mid
14. else:
15. right -= 1
16.
17. return nums[left]
18.
19.
20.if __name__ == "__main__":
21. solution = Solution()
22.
23. # 测试示例1
24. nums_1 = [4, 5, 6, 7, 0, 1, 2]
25. result_1 = solution.findMin(nums_1)
26. print(f"The minimum element in {nums_1} is: {result_1}")
27.
28. # 测试示例2
29. nums_2 = [3, 4, 5, 1, 2]
30. result_2 = solution.findMin(nums_2)
31. print(f"The minimum element in {nums_2} is: {result_2}")
32.
33. # 测试示例3
34. nums_3 = [1]
35. result_3 = solution.findMin(nums_3)
36. print(f"The minimum element in {nums_3} is: {result_3}")
4.3 运行结果
