LeetCode Hot100 刷题笔记（9）—— 二分查找、技巧

目录

前言

一、二分查找

1. 搜索插入位置

2. 搜索二维矩阵

3. 在排序数组中查找元素的第一个和最后一个位置

4. 搜索旋转排序数组

5. 寻找旋转排序数组中的最小值

6. 寻找两个正序数组的中位数

二、技巧

1. 只出现一次的数字

2. 多数元素

3. 颜色分类

4. 下一个排列

5. 寻找重复数

---

前言

一、二分查找：搜索插入位置，搜索二维矩阵，在排序数组中查找元素的第一个和最后一个位置，搜索旋转排序数组，寻找旋转排序数组中的最小值，寻找两个正序数组的中位数。

二、技巧：只出现一次的数字，多数元素，颜色分类，下一个排列，寻找重复数。

---

一、二分查找

1. 搜索插入位置

原题链接：35. 搜索插入位置 - 力扣（LeetCode）

# 解法（1）
class Solution(object):def searchInsert(self, nums, target):if target in nums:return nums.index(target)else:nums.insert(0, float('-inf'))nums.insert(len(nums), float('inf'))for i, n in enumerate(nums):if nums[i] < target and nums[i+1] > target:return i# 解法（2）
class Solution(object):def searchInsert(self, nums, target):for k,v in enumerate(nums):if target<=max(nums):if v<target:continuereturn kelse:return len(nums)

2. 搜索二维矩阵

原题链接：74. 搜索二维矩阵 - 力扣（LeetCode）

class Solution(object):def searchMatrix(self, matrix, target):matrix = sum(matrix, [])if target in matrix:return Truereturn False

3. 在排序数组中查找元素的第一个和最后一个位置

原题链接：34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

# 解法（1）
class Solution(object):def searchRange(self, nums, target):if target not in nums:return [-1, -1]else:left = nums.index(target)nums.sort(reverse=True)right = len(nums)- nums.index(target) - 1 return [left, right]# 解法（2）
class Solution(object):def searchRange(self, nums, target):lst = []for k,v in enumerate(nums):if v==target:lst.append(k)if not lst:lst = [-1,-1]return [min(lst), max(lst)]

4. 搜索旋转排序数组

原题链接：33. 搜索旋转排序数组 - 力扣（LeetCode）

class Solution(object):def search(self, nums, target):if target in nums:return nums.index(target)else:return -1

5. 寻找旋转排序数组中的最小值

原题链接：153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

class Solution(object):def findMin(self, nums):return min(nums)

6. 寻找两个正序数组的中位数

原题链接：4. 寻找两个正序数组的中位数 - 力扣（LeetCode）

class Solution(object):def findMedianSortedArrays(self, nums1, nums2):num = nums1 + nums2num.sort()ln = len(num) if ln % 2 == 0:mid = (num[ln//2-1] + num[ln//2]) / 2.0else:mid = num[ln//2]return mid

二、技巧

1. 只出现一次的数字

原题链接：136. 只出现一次的数字 - 力扣（LeetCode）

# 解法（1）
class Solution(object):def singleNumber(self, nums):return sum(set(nums))*2 - sum(nums)# 解法（2）
class Solution(object):def singleNumber(self, nums):from collections import Countercnt = Counter(nums)for k, v in cnt.items():if v == 1:return k

2. 多数元素

原题链接：169. 多数元素 - 力扣（LeetCode）

# 解法（1）
class Solution(object):def majorityElement(self, nums):nums.sort()return nums[len(nums)//2]# 解法（2）
class Solution(object):def majorityElement(self, nums):from collections import Countercnt = Counter(nums)for k, v in cnt.most_common(1):return k

3. 颜色分类

原题链接：75. 颜色分类 - 力扣（LeetCode）

class Solution(object):def sortColors(self, nums):return nums.sort()   

4. 下一个排列

原题链接：31. 下一个排列 - 力扣（LeetCode）

class Solution(object):def nextPermutation(self, nums):# [4,5,2,6,7,3,1]   先找2，在找3i = len(nums) -1while i>0 and nums[i-1]>=nums[i]:i -= 1if i>0:j = len(nums) - 1while nums[j] <= nums[i-1]:j -= 1nums[i-1], nums[j] = nums[j], nums[i-1]nums[i:] = sorted(nums[i:])

5. 寻找重复数

原题链接：287. 寻找重复数 - 力扣（LeetCode）

# 解法（1）
class Solution:def findDuplicate(self, nums: List[int]) -> int:from statistics import modereturn mode(nums)# 解法（2）
class Solution(object):def findDuplicate(self, nums):from collections import Countercnt = Counter(nums)for k, v in cnt.most_common(1):return k