四种方法,不同角度解释

数组中重复的数字

http://www.nowcoder.com/questionTerminal/623a5ac0ea5b4e5f95552655361ae0a8

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        #方法一  排序后再遍历 时间O(n*logn) 空间O(1)
        if (not numbers)&nbs***bsp;len(numbers) == 1:
            return False
        numbers.sort()
        temp = numbers[0]
        for i in range(1,len(numbers)):
            if temp == numbers[i]:
                duplication[0] = temp
                return True
            temp = numbers[i]
        return False

        #方法二  使用哈希表 时间O(1)  空间O(n)
        dic = {}
        for i in numbers:
            if i in dic and dic[i] == 1:
                duplication[0] = i
                return True
            dic[i] = 1
        return False
        #方法三  下标定位法 时间O(n) 空间O(1)
        for i in range(len(numbers)):
            while i != numbers[i]:
                if numbers[i] == numbers[numbers[i]]:
                    duplication[0] = numbers[i]
                    return True                    
                temp = numbers[i]
                numbers[i] = numbers[temp]
                numbers[temp] = temp
        return False

        #  方法四  使用内置函数
        import collections
        if len(numbers) == len(set(numbers)):
            return False
        duplication[0] = collections.Counter(numbers).most_common(1)[0][0]
        return True
        
    

全部评论

相关推荐

07-02 18:09
门头沟学院 Java
苍穹外卖和谷粒商城这俩是不是烂大街了,还能做吗?
想去重庆的鸽子在吐槽:你不如把这俩做完自己搞明白再优化点再来问 何必贩卖焦虑
点赞 评论 收藏
分享
05-23 20:31
已编辑
武汉大学 Java
内向的柠檬精在研究求...:注意把武大标粗标大 本地你俩不是乱杀
实习进度记录
点赞 评论 收藏
分享
评论
22
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务