Answer:
brainliest if it did help you
Explanation:
Given array : A[0...n-1]Now, create a count array Cnt[0...n-1]then, initialize Cnt to zero
for(i=0...n-1)
Cnt[i]=0 ---------O(n) time
Linearly traverse the list and increment the count of respected number in count array.
for(i=0...n-1)
Cnt[A[i]]++; ---------O(n) time
Check in the count array if duplicates exist.
for(i=0...n-1){
if(C[i]>1)
output (i); -----------O(n) time
}
analysis of the above algorithm:
Algorithm takes = O(1 + n + n + n)
= O(n)
//java code
public class SortIntegers {
public static void sort(int[] arr) {
int min = arr[0];
int max = arr[0];
for (int i = 0; i < arr.length; ++i) {
if (arr[i] > max) {
max = arr[i];
}
if (arr[i] < min) {
min = arr[i];
}
}
int counts[] = new int[max - min + 1];
for (int i = 0; i < arr.length; ++i) {
counts[arr[i] - min]++;
}
for (int i = 0; i < counts.length; ++i) {
if (counts[i] > 1) {
System.out.print((i + min) + " ");
}
}
System.out.println();
}
public static void main(String[] args) {
sort(new int[] { 5, 4, 10, 2, 4, 10, 5, 3, 1 });
}
}
