Write a program to print all the duplicate elements in a given array where the elements of array are from 0 to n-1 . For example if the given array is {3,1,3,5,1,3,5,9,5,9,9,3,6,4} then output should be {3,1,5,9}.
Method 1 (Brute force )
Algorithm :
1) for i=0 ; i< n;i++ where n is the number of elements in array
2) for j=i ;j<n;j++
2.1) if a[i]==a[j] then print a[i]
2.2) else do nothing .
Time Complexity : O(n*n)
Method 2(Sorting )
Algorithm :
1) Sort the array using best sorting methods(Quick,Merge or Heap )
2) Run the loop ( for i=1;i<n;i++) where n is the number of elements in an array.
3) if(a[i]==a[i-1]) then print a[i].
4) else do nothing .
Time Complexity : O(nlogn) because of nlogn time complexity of sorting algorithm
Method 3 (Hashing)
Algorithm :
1) Create an array count[] with 256 in length. and initialize with 0.
2) for i=0;i<n;i++
3) if (count[a[i]]==0) then increment count[a[i]]++;
4) else if (count[a[i]]>0) then print a[i];
Time Complexity : O(n)
Method 1 (Brute force )
Algorithm :
1) for i=0 ; i< n;i++ where n is the number of elements in array
2) for j=i ;j<n;j++
2.1) if a[i]==a[j] then print a[i]
2.2) else do nothing .
Time Complexity : O(n*n)
Method 2(Sorting )
Algorithm :
1) Sort the array using best sorting methods(Quick,Merge or Heap )
2) Run the loop ( for i=1;i<n;i++) where n is the number of elements in an array.
3) if(a[i]==a[i-1]) then print a[i].
4) else do nothing .
Time Complexity : O(nlogn) because of nlogn time complexity of sorting algorithm
Method 3 (Hashing)
Algorithm :
1) Create an array count[] with 256 in length. and initialize with 0.
2) for i=0;i<n;i++
3) if (count[a[i]]==0) then increment count[a[i]]++;
4) else if (count[a[i]]>0) then print a[i];
Time Complexity : O(n)
No comments:
Post a Comment