[python3] 3_01 数组中重复的数字
2019-01-27 本文已影响0人
cca1yy
题目如下
题目.png
思路1
将输入数组排序，从头到尾扫描排序后的数组。
代码如下
# 03_01_FindDuplication.py
class Solution(object):
def duplicate(self, number, length):
"""
:type number: list[int]
:type length: int
:type duplication: list
:rtype: list[int]
"""
# 若传入的数组为空或者参数不对
if number == [] or length < 0:
return False
#判断传入的数组number内每个数组元素值是否位于0~length - 1的范围内
for nn in number:
if nn <0 or nn > length - 1:
return False
# 若传入的参数没有问题，则将检查到的重复的参数放入数组duplication中(事先判断duplication中是否包含当前检查出的元素)
duplication = []
number.sort()
for i in range(0, length - 1):
if number[i] == number[i + 1]:
if number[i] not in duplication:
duplication.append(number[i])
return duplication
# 测试用例
## 符合题目要求的输入
number = [2, 1, 3, 1, 4]
length = 5
a = Solution()
aa = a.duplicate(number, length)
print("---test1---")
for aaa in aa:
print(aaa)
# 输入空的数组
number2 = []
length2 = 0
b = Solution()
bb = b.duplicate(number2, length2)
print("---test2---")
print(bb)
# 2个重复元素
number3 = [1, 2, 4, 6, 2, 4, 3]
length3 = 7
c = Solution()
cc = c.duplicate(number3, length3)
print("---test3---")
for ccc in cc:
print(ccc)
# 2个重复元素，其中元素2重复3次，元素4重复2次
number4 = [1, 2, 4, 5, 2, 2, 4]
length4 = 7
d = Solution()
dd = d.duplicate(number4, length4)
print("---test4---")
for ddd in dd:
print(ddd)
# 无重复元素
number5 = [1, 2, 3, 4, 5]
length5 = 5
e = Solution()
ee = e.duplicate(number5, length5)
print("---test5---")
print(ee)
运行结果
测试用例运行结果
可以看出，此程序返回所有重复数字。
思路2
利用哈希表来解决问题。
PS: 这里用到collections模块的Counter()函数。
代码如下
#03_01_FindDuplication_1.py
class Solution(object):
def duplicate(self, number, length):
"""
:type number: list[int]
:type length: int
:type duplication: list
:rtype: list[int]
"""
# 若传入的数组为空或者参数不对
import collections
if number == [] or length < 0:
return False
#判断传入的数组number内每个数组元素值是否位于0~length - 1的范围内
for nn in number:
if nn <0 or nn > length - 1:
return False
# 若传入的参数没有问题，则将检查到的重复的参数放入数组duplication中(事先判断duplication中是否包含当前检查出的元素)
duplication = []
key_dict = {}
key_dict = collections.Counter(number)
for key, count in key_dict.items():
if count != 1:
if key not in duplication:
duplication.append(key)
return duplication
# 测试用例
## 符合题目要求的输入
number = [2, 1, 3, 1, 4]
length = 5
a = Solution()
aa = a.duplicate(number, length)
print("---test1---")
for aaa in aa:
print(aaa)
# 输入空的数组
number2 = []
length2 = 0
b = Solution()
bb = b.duplicate(number2, length2)
print("---test2---")
print(bb)
# 2个重复元素
number3 = [1, 2, 4, 6, 2, 4, 3]
length3 = 7
c = Solution()
cc = c.duplicate(number3, length3)
print("---test3---")
for ccc in cc:
print(ccc)
# 2个重复元素，其中元素2重复3次，元素4重复2次
number4 = [1, 2, 4, 5, 2, 2, 4]
length4 = 7
d = Solution()
dd = d.duplicate(number4, length4)
print("---test4---")
for ddd in dd:
print(ddd)
# 无重复元素
number5 = [1, 2, 3, 4, 5]
length5 = 5
e = Solution()
ee = e.duplicate(number5, length5)
print("---test5---")
print(ee)
运行结果
测试用例运行结果
可以看出，此程序返回所有重复数字。
思路3
由于长度为n的数组里的所有数字都在0~n-1的范围内，若数组内的数字都没有重复，则数组排序后下标i对应的数字也为i。因此可以从数组的第一个元素开始扫描，若下标与数组元素值相等，则接着扫描下一个数字；若下标与数组元素值不相等，则判断当前数组元素值与下标为当前数组元素值对应的数字是否相等。若相等，则当前数组元素值重复，返回当前数组元素值，若不相等，则将当前数组元素换到对应下标处。重复上述过程，知道发现重复数字为止。
代码如下
#03_01_FindDuplication_2.py
class Solution(object):
def duplicate(self, number, length):
"""
:type number: list[int]
:type length: int
:type duplication: list
:rtype: list[int]
"""
# 若传入的数组为空或者参数不对
if number == [] or length < 0:
return False
#判断传入的数组number内每个数组元素值是否位于0~length - 1的范围内
for nn in number:
if nn <0 or nn > length - 1:
return False
# 若传入的参数没有问题，则将检查到的重复的参数放入数组duplication中(事先判断duplication中是否包含当前检查出的元素)
duplication = []
for i in range(0, length):
if number[i] == i:
pass
else:
if number[i] == number[number[i]]:
if number[i] not in duplication:
duplication.append(number[i])
else:
pass
else:
tmp = number[i]
number[i] = number[tmp]
number[tmp] = tmp
#for nn in number:
#print(nn)
#print("---")
return duplication
# 测试用例
## 符合题目要求的输入
number = [2, 1, 3, 1, 4]
length = 5
a = Solution()
aa = a.duplicate(number, length)
print("---test1---")
for aaa in aa:
print(aaa)
# 输入空的数组
number2 = []
length2 = 0
b = Solution()
bb = b.duplicate(number2, length2)
print("---test2---")
print(bb)
# 2个重复元素
number3 = [1, 2, 4, 6, 2, 4, 3]
length3 = 7
c = Solution()
cc = c.duplicate(number3, length3)
print("---test3---")
for ccc in cc:
print(ccc)
# 2个重复元素，其中元素2重复3次，元素4重复2次
number4 = [1, 2, 4, 5, 2, 2, 4]
length4 = 7
d = Solution()
dd = d.duplicate(number4, length4)
print("---test4---")
for ddd in dd:
print(ddd)
# 无重复元素
number5 = [1, 2, 3, 4, 5]
length5 = 5
e = Solution()
ee = e.duplicate(number5, length5)
print("---test5---")
print(ee)
运行结果
测试用例运行结果
可以看出，此程序无法检测数组内所有重复数字，但也满足题意。
新手刷题，若有任何疑问或者问题请留言，欢迎交流~~
