Removing duplicates from an array (no sets or sort)
I have the following code:
import java.util.Scanner;
public class ArrayDuplicates {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.print("How many numbers are you going to enter? ");
int num = scan.nextInt();
int[] arr = new int[num]; // initialize array with user inputted length
for (int i = 0; i < arr.length; i++) { // enter numbers into array
arr[i] = scan.nextInt();
}
int[] unique = new int[arr.length]; //initialize new array that will hold unique values
for (int i = 0; i < arr.length; i++) {
boolean b = true; //boolean that checks if an element is a duplicate
for (int j = i+1; j < arr.length; j++) { //check all elements above int i
if (arr[i] == arr[j]) {
b = false; // set b to false if there is an existing duplicate
}
}
if (b) {
unique[i] = arr[i]; // if no duplicates exist, then it is unique.
}
}
for (int i = 0; i < unique.length; i++) {
System.out.println(unique[i]);
}
}
}
The problem with this code (other than being terribly slow for large arrays, but that's not the point) is that since undeclared elements for the array unique
will be set to 0
, duplicate elements from the first array are set to 0
in unique[]
(if that makes sense). I understand why this is happening, but cannot find an efficient way to fix it. I tried to set the duplicate elements to Integer.MIN_VALUE
in a unique array and then print only those elements unique[]
that are not equal Integer.MIN_VALUE
, but that seems like a weak solution to the problem. How can I fix this problem?
EDIT: If I run the code:
How many numbers are you going to enter? 4
1
2
2
0
Output:
1 0 2 0
Since the second element of the array is a duplicate, I don't set unique[1]
to any value, making it default to 0. How can I avoid printing this 0 since it is not part of the original array?
EDIT 2: Yes, this is homework, but the reason I don't want to use sets, sorting, etc. is primarily because I am not familiar with them. Also, since I am not asking anyone to write the entire program for me, I think it is okay to ask for a little help.
source to share
I'm going to use the tools you used to solve the problem because something in me tells me this is homework ...
import java.util.Scanner;
public class ArrayDuplicates
{
public static void main(String[] args)
{
Scanner scan = new Scanner(System.in);
System.out.print("How many numbers are you going to enter? ");
int num = scan.nextInt();
int[] arr = new int[num]; // initialize array with user inputted length
for (int i = 0; i < arr.length; i++)// enter numbers into array
{
arr[i] = scan.nextInt();
}
double[] unique = new double[arr.length]; //initialize new array that will hold unique values
///////My edit
for(int z = 0; z < unique.length; z++)
{
unique[z] = -0.5;
}
///////
for (int i = 0; i < arr.length; i++)
{
boolean b = true; //boolean that checks if an element is a duplicate
for (int j = i+1; j < arr.length; j++) //check all elements above int i
{
if (arr[i] == arr[j])
{
b = false; // set b to false if there is an existing duplicate
}
}
if (b)
{
unique[i] = arr[i]; // if no duplicates exist, then it is unique.
}
}
for (int i = 0; i < unique.length; i++)
{
if(!(unique[i] == -0.5))
{
System.out.println((int)(unique[i]));
}
}
}
}
So can you see where I commented out my edit? that a new thing, a very simple way to test, is to give values to a number not expected in this case, a negative number. Now, this is an assumption on my part, change -1 to whatever value you know will not be entered into this Scanner
. The same goes for the if statement.
source to share
Whatever value you choose (zero, min-int, max-int) to represent the deleted duplicate is a problem. The user can always enter this number and your program will behave incorrectly. (The only way you could legitimately use (say) min-int or max-int would be if the requirements clearly state that the number is invalid input.)
The correct way to handle duplicates is to keep a counter of the number of non-duplicates and make sure the duplicates (or the slots that will contain them) are at the top end of the array; that is, indices> = counter. (This becomes the invariant that your algorithm should support ...)
The best solution is to eliminate duplicates before adding them to the array. Keep counting the number of non-duplicates and iterating until it reaches your num
... not the length of the array.
But if you want to add all the values to the array and then eliminate duplicates when you find a duplicate, you need to swap the elements so that you can maintain the invariant. The logic is a little hesitant ... but quite doable.
UPDATE
I just noticed that your original solution uses two arrays. I assumed you are using a single array and doing an in-place update to eliminate duplicates.
source to share
The best way to do this is by using the Map .
public interface Map<K,V>
An object that maps keys to values. The card cannot contain duplicate keys; each key can display at most one value.
I don’t know why you don’t want to use the kit if you don’t do your homework ...
If you really can't use the kit . Go ahead and create ArrayList
. Store the elements array
internally, but every time you want to keep, you check if the element is already a part ArrayList
.
int [] list = {5, 5, 3, 2, 5, 3, 5};
ArrayList<Integer> list2 = new ArrayList<Integer>();
for(int i = 0; i < list.length; i++)
if(!list2.contains(list[i]))
list2.add(list[i]);
You can, if you like, cast it ArrayList
back into an array.
Object[] list3 = list2.toArray();
source to share
You can store the maximum value entered by the user (when the user enters values in the first loop) and then assigns the default value for the unique value to be max + 1.
Or you can try a different approach to solve the problem, something like this:
int num = scan.nextInt();
int[] arr = new int[num];
int[] uniq = new int[num+1000000];
int j = 0;
// enter numbers into array
for (int i = 0; i < arr.length; i++) {
int input = scan.nextInt();
if(uniq[input] != 1){
uniq[input] = 1;
arr[j] = input;
j++;
}
}
for (int i = 0; i < j; i++) {
System.out.println(arr[i]);
}
Note that this solution is on the assumption that the user will not enter a number greater than (num + 1,000,000)
.
source to share
This solution allows you to enter any integer value, even negative. This is the same code with some modifications and added a parallel array for comparison. He also removed some lines of code that are no longer needed.
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
System.out.print("How many numbers are you going to enter? ");
int num = scan.nextInt();
int[] arr = new int[num]; // initialize array with user inputted length
int[] arrflag = new int[num];
for (int i = 0; i < arr.length; i++) { // enter numbers into array
System.out.print("Enter number: ");
arr[i] = scan.nextInt();
arrflag[i] = 0;
}
int[] unique = new int[arr.length]; //initialize new array that will hold unique values
int n=0;
for (int i = 0; i < arr.length; i++) {
if (arrflag[i] == 0) {
unique[n++] = arr[i];
for (int j = i+1; j < arr.length; j++) { //check all elements above int i
if (arr[i] == arr[j]) {
arrflag[j]=-1;
}
}
}
}
for (int i = 0; i < n; i++) {
System.out.println(unique[i]);
}
}
source to share
Create a parallel character array with all values as .. Whenever you find a duplicate, set the value to ',' in the character array. Then print only the values of your array with a matching "." in the character array.
}
System.out.println();
for (int i = 0; i < arr.length; i++) {
if(a[i]=='.')
System.out.println(arr[i]);
}
}
}
source to share
Example with the string [].
public static List<String> arrListWithNoDups(String arr[]){
Map<String, Integer>map = new HashMap<String, Integer>();
List<String>list = new ArrayList<String>();
for(int i = 0; i<arr.length; i++){
if(map.get(arr[i]) == null){
map.put(arr[i], 0);
}
else{
map.put(arr[i], map.get(arr[i])+1);
}
}
for(int j = 0; j<arr.length; j++){
if(map.get(arr[j])==0){
list.add(arr[j]);
}
}
return list;
}
source to share
public class RemoveDuplicateFromArray {
public static void main(String[] args) {
int[] myArray = {1, 2, 1, 4, 1, 5, 2, 5};
System.out.println("Before removing duplicate" + Arrays.toString(myArray));
RemoveDuplicateFromArray rd = new RemoveDuplicateFromArray();
int[] newArray = rd.findDuplicate(myArray);
System.out.println("Before removing duplicate" + Arrays.toString(newArray));
}
public int[] findDuplicate(int[] inputArray) {
Arrays.sort(inputArray);
int count = 0;
for (int i = 0; i < inputArray.length; i++) {
if (i + 1 < inputArray.length && inputArray[i] == inputArray[i + 1]) {
count++;
}
}
int[] result = new int[inputArray.length - count];
int c = 0;
for (int j = 0; j < inputArray.length; j++) {
if (j + 1 < inputArray.length && inputArray[j] == inputArray[j + 1]) {
} else {
result[c] = inputArray[j];
c++;
}
}
inputArray = result;
return inputArray;
}
}
source to share
I tried to improve this code, please comment / suggest if further improvement can be done.
public static int[] removeDuplicate(int[] arr) {
int[] noDuplicates = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
boolean b = true;
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] == arr[j]){
b = false;
}
}
if (b) {
noDuplicates[i] = arr[i];
System.out.print(noDuplicates[i] + " ");
}
}
return noDuplicates;
}
source to share