Case - 1 : By comparing each element with total array = 0(n2)
import java.util.Arrays;
public class NormalWay {
public static void main(String[] args) {
int[] a = new int[] { 1, 2, 3, 4, 4, 5, 7, 3, 4, 5 };
a = removeDuplicateFromArray1(a);
System.out.println(Arrays.toString(a));
}
public static int[] removeDuplicateFromArray1(int[] array) {
int length = array.length;
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length;j++) {
if (array[i] == array[j]) {
array = deleteEleFromArray(array, j);
--length;
}
}
}
return array;
}
public static int[] deleteEleFromArray(int[] array, int pos){
int[] newarray = new int[array.length-1];
int latIndex = 0;
for (int i = 0; i < array.length; i++) {
if(i!=pos)
newarray[latIndex++] =array[i];
}
return newarray;
}
}
|
Case - 2 : By sorting and compare adjacent elements = 0(n)
import java.util.Arrays;
//time complexity is o(n)
public class ByOrderingArray {
public static void main(String[] args) {
int[] a = new int[] { 1, 2, 3, 4, 4, 4, 4, 5, 7, 3, 4, 5 };
a = sortArray(a);
System.out.println(Arrays.toString(a));
a = removeDuplicateFromSorttedArray(a);
System.out.println(Arrays.toString(a));
}
//o(n2)
public static int[] sortArray(int[] array) {
for(int i=0; i<array.length; i++){
for(int j=i+1; j<array.length; j++){
if(array[i] > array[j]){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
return array;
}
//o(n)
public static int[] removeDuplicateFromSorttedArray(int[] array) {
int[] newArray = new int[array.length];
int index = 1;
newArray[0] = array[0];
for(int i=1; i<array.length; i++){
if(array[i] != array[i-1]){
newArray[index++] = array[i];
}
}
return newArray;
}
}
|
Case - 3 : By using hashing, compare element in hashset = 0(n)
import java.util.Arrays;
import java.util.HashSet;
public class ByHashing {
public static void main(String[] args) {
Integer[] a = new Integer[] { 1, 2, 3, 4, 4, 4, 4, 5, 7, 3, 4, 5 };
a = removeDuplicateFromArray(a);
System.out.println(Arrays.toString(a));
}
// o(n)
public static Integer[] removeDuplicateFromArray(Integer[] array) {
HashSet<Integer> set = new HashSet<Integer>();
for(int i=0; i<array.length; i++){
if(!set.contains(array[i]))
set.add(array[i]);
}
Integer[] newArray = new Integer[array.length];
return set.toArray(newArray);
}
}
|
No comments:
Post a Comment