Find duplicates unsorted array
class PrintDuplicateAndCounts {
static int[] array;
static int smallest = -1;
static int largest = -1;
// Time complexity : O(n^2). Assuming +ve numbers
static void printDuplicates() {
int count;
for(int i = 0; i < array.length-1; i++) {
if(array[i] > -1) {
count = 1;
for(int j = i+1; j < array.length; j++) {
if(array[i] == array[j]) {
count++;
array[j] = -1;
}
}
if(count > 1) {
System.out.println(array[i] + " appeared " + count + " times.");
}
}
}
}
static void printDuplicates_dp() {
setMinAndMax();
int[] dp = new int[largest - smallest + 1];
for(int i = 0; i < array.length; i++) {
dp[array[i]-smallest]++;
}
for(int i = 0; i < array.length; i++) {
if(dp[array[i]-smallest] > 1) {
System.out.println(array[i] + " appeared " + dp[array[i]-smallest] + " times");
dp[array[i]-smallest] = -1;
}
}
}
static void setMinAndMax() {
for(int i = 0; i < array.length; i++) {
if(array[i] > largest) {
largest = array[i];
}
if(array[i] < smallest) {
smallest = array[i];
}
}
}
public static void main (String[] args) {
array = new int[] {8, 3, 6, 4, 6, 5, 6, 8, 2, 7};
printDuplicates();
array = new int[] {8, 3, 6, 4, 6, 5, 6, 8, 2, 7};
printDuplicates_dp();
}
}
Comments
Post a Comment