leetcode explore 初级算法第四题: 找出不重复的列表

leetcode explore 初级算法第四题。原题链接：

https://leetcode-cn.com/explore/interview/card/top-interview-questions-easy/1/array/24/

题目分析

因为题目不是很长，这里把题目贴出来：

Given an array of integers, find if the array contains any duplicates.

Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Example 1:

Input: [1,2,3,1]
Output: true
Example 2:

Input: [1,2,3,4]
Output: false
Example 3:

Input: [1,1,1,3,3,4,3,2,4,2]
Output: true

题目意思很简单，即如果整个列表是没有重复数字的，返回 False，否则返回 True

参考答案

这个题目本身并不难，因为也没有限制空间复杂度，用 Python 来解决尤其简单，我们可以使用 set 这种数据结构，参考代码如下：

class Solution(object):
    def containsDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        snums = set(nums)
        return len(snums) != len(nums)

题目本身值得讲一讲的地方在于，这个题目涉及到面试经常会问到的一个题目，即：

Python 中如何对列表进行去重？

参考答案如下：

# 如果仅仅是去重
set('b', 'b', 'a', 'a', 'b', 'b', 'a'])

# 如果要保持顺序
# 第一种方法,也是最笨的方法
new_list = [] # 定义一个空的列表
for elem in slist:
    if elem not in new_list:  
        new_list.append(elem)

# 第一种方法可以用 reduce 来
from functools import reduce

#def f(x,y):
#    if y not in x:
#        return x + [y]
#    else:
#        return x

# 上面的等价于：
f = lambda x,y: x if y in x else x + [y]

print(list(reduce(f, [[], 1, 5, 4, 9, 3, 6, 9, 1, 5, 4, 3])))
print(list(reduce(f, [[],'b', 'b', 'a', 'a', 'b', 'b', 'a'])))

# 第二种方法，利用 key 来保证顺序
slist = ['b', 'b', 'a', 'a', 'b', 'b', 'a']
ll = list(set(slist))
ll.sort(key=slist.index)
return ll

# 第三种方法，利用 OrderedDict
from collections import OrderedDict

ordered_dict = OrderedDict.fromkeys(['b', 'b', 'a', 'a', 'b', 'b', 'a'])
list(ordered_dict)

此外，上面提到的第三种方法，在 python3.7 之后，dict 的效果就和 OrderedDict 的效果是一样的了，所以直接可以用 dict 来实现。