10 examples of 'find duplicate in array interviewbit solution' in Python

2
def findDuplicate(self, nums: List[int]) -> int:
3
    p1, p2 = nums[0], nums[nums[0]]
4
    while nums[p1] != nums[p2]:
5
        p1 = nums[p1]
6
        p2 = nums[nums[p2]]
7
    p2 = 0
8
    while nums[p1] != nums[p2]:
9
        p1 = nums[p1]
10
        p2 = nums[p2]
11
    return nums[p1]

29
def main():
30
    sol = Solution()
31
    assert sol.containsNearbyDuplicate([-1, -1], 1)

2
def containsDuplicate(self, nums):
3
    """
4
    :type nums: List[int]
5
    :rtype: bool
6
    """
7
    nums_sort = sorted(nums)
8
    for i, _ in enumerate(nums_sort[:-1]):
9
        if nums_sort[i] == nums_sort[i + 1]:
10
            return True
11
    
12
    return False

4
def repeatedNumber(self, A):
5
    '''
6
    # This is the marker concept, by list modification
7
    A = list(A)
8
    if len(A) <= 1:
9
        return -1
10
    for i in range(len(A)):
11
        num = abs(A[i])
12
        if A[num]>=0:
13
            A[num] = -1 * A[num] # marking negative means already visited A[i]
14
        else:
15
            return num
16
    return -1
17
    '''
18
    
19
    # This is modified Floyd Warshall concept, cycle in linked list type
20
    # https://medium.com/solvingalgo/solving-algorithmic-problems-find-a-duplicate-in-an-array-3d9edad5ad41
21
    
22
    slow, fast = A[0], A[A[0]]
23
    while slow!=fast:
24
        slow = A[slow]
25
        fast = A[A[fast]]
26
    # the slow and fast pointers are at the same point now, i.e start point of cycle
27
    slow = 0
28
    while slow!=fast:
29
        slow = A[slow]
30
        fast = A[fast]
31
    if slow == 0:
32
        return -1
33
    else:
34
        return slow

10
def removeDuplicates(self, nums):
11
    """
12
    :type nums: List[int]
13
    :rtype: int
14
    """
15
    if len(nums) == 0:
16
        return 0
17
    flag, count  = 0, 0
18
    for i in xrange(1,len(nums)):
19
        if nums[count] == nums[i] and flag == 0:
20
            count += 1
21
            nums[count], nums[i] = nums[i], nums[count]
22
            flag = 1
23
        elif nums[count] != nums[i]:
24
            count += 1
25
            nums[count], nums[i] = nums[i], nums[count]
26
            flag = 0
27
    return count+1

51
def subsetsWithDup(self, nums):
52
    """
53
    :type nums: List[int]
54
    :rtype: List[List[int]]
55
    """
56
    result = []
57
    self.subsetsWithDupRecu(result, [], sorted(nums))
58
    return result

6
def removeDuplicates(self, nums: List[int]) -> int:
7
    if len(nums) == 0: return 0
8
    j = 1
9
    for i in range(1, len(nums)):
10
        if nums[i] != nums[i-1]:
11
            nums[j] = nums[i]
12
            j += 1
13
    return j

2
def removeDuplicates(self, nums: List[int]) -> int:
3
    if not nums :
4
        return 0
5
    j = 1
6
    for i in range( 1 , len(nums)):
7
        if nums[i] != nums[i - 1] :
8
            nums[j] = nums[i]
9
            j += 1
10
    return j

47
def removeDuplicates_another_loop_style(self, A):
48
    """
49
    Yet another looping style - double while loops
50
    :param A: list
51
    :return: "shrunk" list
52
    """
53
    length = len(A)
54
55
    if length==0 or length==1:
56
        return length
57
58
    closed_ptr = 0
59
    open_ptr = 1
60
    while open_ptr

5
def checkPossibility(self, nums):
6
        """
7
        :type nums: List[int]
8
        :rtype: bool
9
        """
10
        modified, prev = False, nums[0]
11
        for i in xrange(1, len(nums)):
12
            if prev > nums[i]:
13
                if modified:
14
                    return False
15
                if i-2 < 0 or nums[i-2] <= nums[i]:
16
                    prev = nums[i]    # nums[i-1] = nums[i], prev = nums[i]
17
#               else:
18
#                   prev = nums[i-1]  # nums[i] = nums[i-1], prev = nums[i]
19
                modified = True
20
            else:
21
                prev = nums[i]
22
        return True