classSolution:defmajorityElement(self, nums: List[int])->int:
res = nums[0]
count =1for i in nums[1:]:if i == res:
count +=1else:
count -=1if count ==0:
res = i
count =1return res
3. 颜色分类
题目描述 给定一个包含红色、白色和蓝色、共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。这里使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
classSolution:defsortColors(self, nums: List[int])->None:"""
Do not return anything, modify nums in-place instead.
"""
n =len(nums)
zero =-1
two = n
i =0while i < two:if nums[i]==1:
i +=1elif nums[i]==0:
zero +=1
nums[zero], nums[i]= nums[i], nums[zero]
i +=1else:# 注意nums[i] = 2时,i不加1
two -=1
nums[two], nums[i]= nums[i], nums[two]
classSolution:defnextPermutation(self, nums: List[int])->None:"""
Do not return anything, modify nums in-place instead.
"""# 数字倒序排列组成的数字,字典序最大defreverse(nums, left, right):
l = left
r = right
while l <= r:
nums[l], nums[r]= nums[r], nums[l]
l +=1
r -=1
n =len(nums)if n <=1:return nums
# 从后向前查找第一个正序对,倒序排列的部分字典序已经是最大了,没有调整的余地了for i inrange(n -2,-1,-1):if nums[i]< nums[i +1]:
j = n -1# 在右边倒序的部分中找到大于nums[i]的最小数字,和nums[i]进行交换while j > i:if nums[j]> nums[i]:
nums[i], nums[j]= nums[j], nums[i]# 此时i右边仍是倒序,翻转成正序,正序是字典序最小的排列方式
reverse(nums, i +1, n -1)return
j -=1# 如果到了这一步说明整个序列都是倒序,那么直接翻转即可
reverse(nums,0, n -1)
5. 寻找重复数
题目描述 给定一个包含 n + 1 个整数的数组,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。