每日一题【20220412】

题目

Non-Repeating Element(查找第一个没有重复的数组元素)

Difficulty Level : Easy

Find the first non-repeating element in a given array of integers.

Example:

Input : -1 2 -1 3 2
Output : 3
Explanation : The first number that does not 
repeat is : 3

Input : 9 4 9 6 7 4
Output : 6

解题思路

• A Simple Solution is to use two loops. The outer loop picks elements one by one and inner loop checks if the element is present more than once or not.

  Implementation:

  # Python3 program to find first
  # non-repeating element.
  
  def firstNonRepeating(arr, n):
  
  	for i in range(n):
  		j = 0
  		while(j < n):
  			if (i != j and arr[i] == arr[j]):
  				break
  			j += 1
  		if (j == n):
  			return arr[i]
  	
  	return -1
  	
  # Driver code
  arr = [ 9, 4, 9, 6, 7, 4 ]
  n = len(arr)
  print(firstNonRepeating(arr, n))
  
  # This code is contributed by Anant Agarwal.

Output :

6

• An Efficient Solution is to use hashing.
  (1) Traverse array and insert elements and their counts in hash table.
  (2) Traverse array again and print first element with count equals to 1.

  # Efficient Python3 program to find first
  # non-repeating element.
  from collections import defaultdict
  
  def firstNonRepeating(arr, n):
  	mp = defaultdict(lambda:0)
  
  	# Insert all array elements in hash table
  	for i in range(n):
  		mp[arr[i]] += 1
  
  	# Traverse array again and return
  	# first element with count 1.
  	for i in range(n):
  		if mp[arr[i]] == 1:
  			return arr[i]
  	return -1
  
  # Driver Code
  arr = [9, 4, 9, 6, 7, 4]
  n = len(arr)
  print(firstNonRepeating(arr, n))
  
  # This code is contributed by Shrikant13

Output:

6

Time Complexity: O(n)
Auxiliary Space: O(n)

• Further Optimization: If array has many duplicates, we can also store index in hash table, using a hash table where value is a pair. Now we only need to traverse keys in hash table (not complete array) to find first non repeating.

  Printing all non-repeating elements:

  # Efficient Python program to print all non-
  # repeating elements.
  
  def firstNonRepeating(arr, n):
  	
  	# Insert all array elements in hash
  	# table
  	mp={}
  	for i in range(n):
  		if arr[i] not in mp:
  			mp[arr[i]]=0
  		mp[arr[i]]+=1
  		
  	# Traverse through map only and
  	for x in mp:
  		if (mp[x]== 1):
  			print(x,end=" ")
  			
  # Driver code
  arr = [ 9, 4, 9, 6, 7, 4 ]
  n = len(arr)
  firstNonRepeating(arr, n)
  
  # This code is contributed by shivanisinghss2110

  

参考资料

1. Non-Repeating Element ↩