今天练习了各种排序,总结了可以用异或解决的题目特征
leetcode(排序):
https://leetcode-cn.com/problems/sort-an-array/submissions/
桶排序
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
if not nums or len(set(nums)) == 1 :
return nums
max_num = max(nums)
min_num = min(nums)
bucket_num = len(nums)
# init bucket
bucket_list = [[] for _ in range(bucket_num)]
# select
for num in nums:
bucket_list[int((num-min_num)*(len(nums)-1)/(max_num-min_num))].append(num)
# sort
result = []
for bucket in bucket_list:
if bucket:
bucket.sort()
for bucket in bucket_list:
for num in bucket:
result.append(num)
return result
快速排序
双边循环法
class Solution:
def quick_sort(self,nums,start,end):
if start >= end:
return
mid = self.sort(nums,start,end)
self.quick_sort(nums,start,mid-1)
self.quick_sort(nums,mid+1,end)
def sort(self,nums,start,end):
if start >= end:
return
mark = start
while start < end:
while nums[end] > nums[mark] and start < end:
end -= 1
while nums[start] <= nums[mark] and start < end:
start += 1
if start < end:
nums[end] ^= nums[start]
nums[start] ^= nums[end]
nums[end] ^= nums[start]
if nums[mark] != nums[end]:
nums[mark] ^= nums[end]
nums[end] ^= nums[mark]
nums[mark] ^= nums[end]
return end
def sortArray(self, nums: List[int]) -> List[int]:
# 快排
self.quick_sort(nums,0,len(nums)-1)
return nums
单边循环法
class Solution:
def sort(self,nums,start,end):
if start >= end:
return
mark = start
for cnt in range(start+1,end+1):
if nums[cnt] < nums[start]:
mark += 1
if mark != cnt:
nums[mark] ^= nums[cnt]
nums[cnt] ^= nums[mark]
nums[mark] ^= nums[cnt]
if mark != start:
nums[mark] ^= nums[start]
nums[start] ^= nums[mark]
nums[mark] ^= nums[start]
self.sort(nums,start,mark-1)
self.sort(nums,mark+1,end)
def sortArray(self, nums: List[int]) -> List[int]:
# 快排
self.sort(nums,0,len(nums)-1)
return nums
非递归
class Solution:
def sort(self,nums,start,end):
mark = start
for cnt in range(start+1,end+1):
if nums[cnt] < nums[start]:
mark += 1
if mark != cnt:
nums[mark] ^= nums[cnt]
nums[cnt] ^= nums[mark]
nums[mark] ^= nums[cnt]
if mark != start:
nums[mark] ^= nums[start]
nums[start] ^= nums[mark]
nums[mark] ^= nums[start]
return mark
def sortArray(self, nums: List[int]) -> List[int]:
# 快排
stack = []
stack.append({"start":0,"end":len(nums)-1})
while(stack):
dic = stack.pop()
mark = self.sort(nums,dic["start"],dic["end"])
if dic["start"] < mark-1:
stack.append({"start":dic["start"],"end":mark-1})
if dic["end"] > mark+1:
stack.append({"start":mark+1,"end":dic["end"]})
return nums
区间优化后的鸡尾酒排序
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
# 鸡尾酒排序
right_border = len(nums)-1
left_border = 0
for i in range(len(nums)//2):
not_sorted = True
# 奇数轮
last_change_index = right_border-1
for j in range(left_border,right_border):
if nums[j] > nums[j+1]:
nums[j] ^= nums[j+1]
nums[j+1] ^= nums[j]
nums[j] ^= nums[j+1]
not_sorted = False
last_change_index = j
right_border = last_change_index
if not_sorted:
break
not_sorted = True
# 偶数轮
last_change_index = left_border+1
for j in range(right_border,left_border,-1):
if nums[j] < nums[j-1]:
nums[j] ^= nums[j-1]
nums[j-1] ^= nums[j]
nums[j] ^= nums[j-1]
not_sorted = False
last_change_index = j
left_border = last_change_index
if not_sorted:
break
return nums
异或
知识点
- 相同为0,不同为1(真值表)
- 0异或任何一个数还是这个数本身
- 一个数异或其本身为0
可以用异或解决的题目特征
存在并且只有一个数字会重复奇数次,要找出这个数字是什么
解释
- 出现偶数次的数字异或结果为0(知识点3)
- 异或满足交换律,将所有数字异或起来的值为出现奇数次的数字(知识点2)