How to Find All Duplicates in an Array using Python?

  • Time:2020-09-07 12:26:38
  • Class:Weblog
  • Read:136

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:
Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

Using Python’s Collections.Counter to Find All Duplicates in Array

Using collections.Counter in Python allows us to count the frequencies of the elements in an array or list in Python. Then, we can use the List comprehensions to create a list of the duplicate elements in an array by checking their frequencies. Finally, we need to convert it to set, this allows us to filter out the duplicates in the duplicates.

1
2
3
4
class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        c = collections.Counter(nums)
        return set([x for x in nums if c[x] > 1])
class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        c = collections.Counter(nums)
        return set([x for x in nums if c[x] > 1])

This solution requires O(N) time and O(N) space as we are storing the frequencies in a dictionary object.

–EOF (The Ultimate Computing & Technology Blog) —

Recommend:
Finding the Closest Divisors
Greedy Solution to Reconstruct a 2-Row Binary Matrix
How to Use jOOQ Library to Write SQL in Java using Fluent Style?
Algorithm to Compute the Number of Days Between Two Dates
How to Sort Integers by The Number of 1 Bits?
Using Depth First Search Algorithm to Delete Tree Nodes with Sum
Web Strategies to Start Your SEO Journey
How to Compute the Product of Last K elements in Array using the
How to Write a High-Quality Blog Post in Just 30 Minutes
8 Things To Include In Your Blog Privacy Policy
Share:Facebook Twitter
Comment list
Comment add