首页 > 上网技巧 > 电脑小技巧 > Python判断字符数组中是否所有的字符都只出现过...

Python判断字符数组中是否所有的字符都只出现过一次

时间:2020-03-05 12:21 作者:QQ地带 我要评论

文章目录判断字符数组中是否所有的字符都只出现过一次判断字符是否唯一时间复杂度O(N)算法思路相应代码空间复杂度O(1)算法思路相应代码
判断字符数组中是否所有的字符都只出现过一次
判断字符是否唯一
 
【题目】
给定一个字符类型数组chas[],判断chas中是否所有的字符都只出现过一次,
 
【举例】
chas=[‘a’,‘b’,‘c’],返回True;chas=[‘1’,‘2’,‘1’],返回False。
 
【要求】
按以下两种不同的要求分别实现
 
实现时间复杂度为O(N)的方法。
在保证额外空间复杂度为O(1)的前提下,请实现时间复杂度尽量低的方法。
 
时间复杂度O(N)算法思路
 
字典/集合/列表 统计,
发现再次统计即为重复,否则字符唯一
时间复杂度为O(N)O(N)O(N),空间复杂度为O(N)O(N)O(N)
 
相应代码
# 判断字符唯一,时间复杂度O(N),空间复杂度O(N)
def is_unique_time_first(arr):
d = {}
for i in range(len(arr)):
if arr[i] in d:
return False
else:
d[arr[i]] = 1
return True
# 简单测试
if __name__ == '__main__':
chas = ['a', 'b', 'c'] print(is_unique_time_first(chas)) # True
 
chas = ['1', '2', '1'] print(is_unique_time_first(chas)) # False
 
 
空间复杂度O(1)算法思路
 
先排序,再查看相邻字符是否相同,有相同即为重复,否则字符唯一
选择排序,冒泡排序,插入排序,时间复杂度O(N^2),空间复杂度O(1),满足条件
堆排序,时间复杂度O(NlogN),空间复杂度O(1),满足条件
快速排序,时间复杂度O(NlogN),空间复杂度最低为O(logN)
归并排序,时间复杂度O(NlogN),需要辅助数组,空间复杂度为O(N)
桶排序、基数排序、计数排序等非比较排序,时间复杂度为O(N),但需要额外空间,跟数据情况有关,因此也不满足条件
 
因此最佳采用堆排序实现,时间复杂度为O(NlogN)O(NlogN)O(NlogN),空间复杂度为O(1)O(1)O(1)
 
相应代码
# 判断字符唯一,空间复杂度O(1),时间复杂度O(NlogN)
def is_unique_space_first(arr):
heap_sort(arr)
for i in range(1, len(arr)):
if arr[i] == arr[i - 1]:
return False
return True
 
# 堆排序
def heap_sort(arr):
# 构建大根堆
for i in range(len(arr)):
heap_insert(arr, i)
# 弹出大根堆顶部,升序排序
for i in range(len(arr)):
swap(arr, 0, len(arr) - 1 - i)
heapify(arr, 0, len(arr) - 1 - i)
 
# 大根堆底部插入
def heap_insert(arr, index):
parent = (index - 1) // 2
while parent >= 0 and arr[index] > arr[parent]:
swap(arr, index, parent)
index = parent
parent = (index - 1) // 2
 
# 大根堆顶部调整
def heapify(arr, index, size):
left = 2 * index + 1
while left arr[index]:
if left + 1 arr[left]:
swap(arr, index, left + 1)
index = left + 1
else:
swap(arr, index, left)
index = left
elif left + 1 arr[index]:
swap(arr, index, left + 1)
index = left + 1
else:
break
left = 2 * index + 1
 
# 交换两数
def swap(arr, i, j):
temp = arr[i] arr[i] = arr[j] arr[j] = temp
 
# 简单测试
if __name__ == '__main__':
# 堆排序测试
arr = [5, 3, 7, 1, 4] heap_sort(arr)
print(arr)
print()
 
arr = [1, 3, 4, 2, 5] heap_sort(arr)
print(arr)
print()
 
arr = [8, 5, 2, 9, 4, 2, 9, 9, 6, 8, 9, 1, 6, 3, 4, 5, 9, 6, 8, 5, 7, 3, 5, 6, 6, 7, 9, 6, 4, 8, 9, 4, 7, 5, 9, 2,
2, 6, 1, 8, 3, 2, 5, 4, 6, 6, 7, 2, 1, 5, 7, 1, 7, 3, 2, 6, 1, 9, 6, 2, 3, 4, 9, 1, 3, 1, 6, 8, 1, 3, 1, 2,
2, 5, 6, 2, 1, 4, 3, 5, 6, 8, 1, 8, 9, 1, 8, 1, 8, 3, 4, 4, 3, 1, 9, 6, 9, 5, 8, 7] heap_sort(arr)
print(arr)
print()
 
chas = ['a', 'b', 'c'] print(is_unique_space_first(chas)) # True
 
chas = ['1', '2', '1'] print(is_unique_space_first(chas)) # False

标签: Python
顶一下
(0)
0%
踩一下
(0)
0%

Google提供的广告