3。leetcode在2N的数组中找出

发布时间:2019-10-14 09:21:37编辑:auto阅读(2293)

    1.题目:
    In a array A of size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times.

    Return the element repeated N times.
    例一:

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

    例二:

    Input: [2,1,2,5,3,2]
    Output: 2

    注意:

    4 <= A.length <= 10000
    0 <= A[i] < 10000
    A.length is even
    1. 我的解法:
    class Solution:
        def repeatedNTimes(self, A: List[int]) -> int:
            n = len(A)
            for i in range(0, n):
                if A[i] in (A[i+1:]):
                    return A[i]

    Runtime: 48 ms, faster than 88.03% of Python3 online submissions for N-Repeated Element in Size 2N Array.
    Memory Usage: 14.3 MB, less than 5.12% of Python3 online submissions for N-Repeated Element in Size 2N Array.

    1. 优秀解法:
     def repeatedNTimes(self, A):
            """
            :type A: List[int]
            :rtype: int
            """
            return int((sum(A)-sum(set(A))) // (len(A)//2-1))

    有重复的和减去没有重复的和 再除以长度除以2再减1就是重复的项。

关键字