Little help (duplicate count and display without sorting array)

  • (2 Pages)
  • +
  • 1
  • 2

15 Replies - 7891 Views - Last Post: 07 July 2010 - 04:26 PM Rate Topic: -----

#1 joms999   User is offline

  • New D.I.C Head

Reputation: 8
  • View blog
  • Posts: 22
  • Joined: 24-February 10

Little help (duplicate count and display without sorting array)

Posted 01 July 2010 - 06:17 AM

Hello,

Just a little help here, i just made a program that counts and displays duplicated elements in an array (prints on how many repetition it is duplicated and what is the element repeated).

My problem is, how to get the same output if the array WOULDN'T be sorted, (IF Possible, don't use hashtable/hashmap (coz my instructor didn't discuss it yet)).

My instructor sucks, giving last minute instruction that array shouldn't be sorted, after finishing coding the program with some sorting.

*PS: The CODE is in the attachments (just open the zip file and extract) , i don't want to post it here using a code snippet because the array I'm searching for duplicate has 7000+ elements and would occupy a lot of space here in dreamincode. So pls. don't put lame comments like "we wouldn't do your homework for you".

Thanks people!

This post has been edited by joms999: 01 July 2010 - 06:19 AM


Is This A Good Question/Topic? 1
  • +

Replies To: Little help (duplicate count and display without sorting array)

#2 Luckless   User is offline

  • </luck>
  • member icon

Reputation: 293
  • View blog
  • Posts: 1,146
  • Joined: 31-August 09

Re: Little help (duplicate count and display without sorting array)

Posted 01 July 2010 - 06:23 AM

what you could do is set up a for loop and counter like this ( i don't know the range of your numbers so I will do 1-100):

int counter = 0;
//set up a nested for loop to search for each specific number in the array
for(i = 0, i < 101, i++){
     
     for(int j = 0, j < array.length, j++){
          if(array[j] == i){
               counter++;
          }
     }
//do something with counter...
//then reset it
counter = 0;
}





P.S.

Quote

don't put lame comments like "we wouldn't do your homework for you".


the best way to get help on this forum is to be respectful. None of us are paid so we have no obligation to help those who are rude. Please be polite and we are more than happy to help you out

This post has been edited by Luckless: 01 July 2010 - 06:28 AM

Was This Post Helpful? 0
  • +
  • -

#3 joms999   User is offline

  • New D.I.C Head

Reputation: 8
  • View blog
  • Posts: 22
  • Joined: 24-February 10

Re: Little help (duplicate count and display without sorting array)

Posted 02 July 2010 - 12:52 AM

View PostLuckless, on 01 July 2010 - 05:23 AM, said:

what you could do is set up a for loop and counter like this ( i don't know the range of your numbers so I will do 1-100):

int counter = 0;
//set up a nested for loop to search for each specific number in the array
for(i = 0, i < 101, i++){
     
     for(int j = 0, j < array.length, j++){
          if(array[j] == i){
               counter++;
          }
     }
//do something with counter...
//then reset it
counter = 0;
}





P.S.

Quote

don't put lame comments like "we wouldn't do your homework for you".


the best way to get help on this forum is to be respectful. None of us are paid so we have no obligation to help those who are rude. Please be polite and we are more than happy to help you out


Could you look at the attached file for me... :D
Was This Post Helpful? 1
  • +
  • -

#4 fallenreaper   User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 240
  • Joined: 19-June 10

Re: Little help (duplicate count and display without sorting array)

Posted 02 July 2010 - 01:39 AM

doing Luckless's way would just give an array full of counters. What i would do is as follows:

for loop in a 4 loop is correct, but inside of there, i would remove duplicates as well as doing the counter, that way you wouldnt get confused.


String[] array = new String[10];
for (int i = 0; i < array.length()-1 /*forget if its -1 or not >_>  lol*/; i;;)/>{
  if (Integer.parseInt(array[i])== -1){continue;}
  for (int j = i+1; j < array.length();j++){
    if (Integer.parseInt(array[j]) == -1){continue;}
    if ( array[i] == array[j] ){
      array[j] = "-1";
      counter++;
  }
  System.out.println(array[i] + " has " + counter + " duplicates.");
  counter = 0;
}



I may be ever so slightly off on syntax because im not using eclipse atm... just throwing it out there.

Pretty much... go through the array, and when it finds a dup, replace it with a holder place. If trying to compare a word with -1, skip it (via continue), if it is trying to compare -1 with stuff, continue...

This should work pretty well as is if you dont need to preserve the array at all. :) Many more ways to do stuff, as i am a fan of Nodes and ArrayLists, but well.... doesnt seem like the professor would want you to do that, so i was thinking something basic. :)

This post has been edited by fallenreaper: 02 July 2010 - 01:40 AM

Was This Post Helpful? 0
  • +
  • -

#5 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12302
  • View blog
  • Posts: 45,400
  • Joined: 27-December 08

Re: Little help (duplicate count and display without sorting array)

Posted 02 July 2010 - 04:07 AM

@joms999: We will be happy to look at your code if you post it, using code tags like so :code:. As attachments have been used maliciously in the past, we do not like them here.

I have a snippet Finding the Mode Using a Map, which you may find helpful. Maps associate Keys with Values, and have unique Keys. So you can do this in O(n) time just iterating through your array, then iterating through your Key Set.
Was This Post Helpful? 0
  • +
  • -

#6 joms999   User is offline

  • New D.I.C Head

Reputation: 8
  • View blog
  • Posts: 22
  • Joined: 24-February 10

Re: Little help (duplicate count and display without sorting array)

Posted 02 July 2010 - 05:19 AM

View Postmacosxnerd101, on 02 July 2010 - 03:07 AM, said:

@joms999: We will be happy to look at your code if you post it, using code tags like so :code:. As attachments have been used maliciously in the past, we do not like them here.

I have a snippet Finding the Mode Using a Map, which you may find helpful. Maps associate Keys with Values, and have unique Keys. So you can do this in O(n) time just iterating through your array, then iterating through your Key Set.


I made a code to solve this (very close to solve it, but if you'd help me, thanks). I have no problem for searching 2 duplicates but it has a problem whenever the array "idNo[]", has MORE THAN 2 duplicates/instances. It repeats like:

Duplicates of 2091177 appears in the array: 2
Duplicates of 2091177 appears in the array: 3

*(209177 is the element in the idNo ELEMENT repeated, and after the colon, is the counter)

I can't fix it to just print the final duplicate count of it. Could you correct what I've coded. Thanks # 1 DIC head.
for (int i = 0; i < idNo.length; i++ ) {
     int duplicateCounter = 1;
	for (int j = i + 1; j < idNo.length; j++){
		if(idNo[j] == idNo[i]){
		duplicateCounter++;
	        System.out.println("Duplicates of " + idNo[i]  + " appears in the array: " + duplicateCounter);
		}
	}
}


This post has been edited by joms999: 02 July 2010 - 05:25 AM

Was This Post Helpful? 1
  • +
  • -

#7 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12302
  • View blog
  • Posts: 45,400
  • Joined: 27-December 08

Re: Little help (duplicate count and display without sorting array)

Posted 02 July 2010 - 05:35 AM

Even if you catch all the duplicates on one iteration of the outer loop, you'll still be stuck with some on another iteration. This is a major reason to use a Map. At the very least, you can create an array equal to the size of the largest element, and do something like what I have below, which will increase the count for a given element. This is still O(n), though it takes a lot more memory than the Map.
countArray[dataArray[i]]++;


Was This Post Helpful? 0
  • +
  • -

#8 joms999   User is offline

  • New D.I.C Head

Reputation: 8
  • View blog
  • Posts: 22
  • Joined: 24-February 10

Re: Little help (duplicate count and display without sorting array)

Posted 02 July 2010 - 05:45 AM

View Postmacosxnerd101, on 02 July 2010 - 04:35 AM, said:

Even if you catch all the duplicates on one iteration of the outer loop, you'll still be stuck with some on another iteration. This is a major reason to use a Map. At the very least, you can create an array equal to the size of the largest element, and do something like what I have below, which will increase the count for a given element. This is still O(n), though it takes a lot more memory than the Map.
countArray[dataArray[i]]++;



hmmm.. can you do it in another basic way?... i know how to use the map, but required is just basics. :D
Was This Post Helpful? 1
  • +
  • -

#9 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12302
  • View blog
  • Posts: 45,400
  • Joined: 27-December 08

Re: Little help (duplicate count and display without sorting array)

Posted 02 July 2010 - 05:50 AM

Re-read my last post. You can use a separate array as I suggested. :)
Was This Post Helpful? 0
  • +
  • -

#10 joms999   User is offline

  • New D.I.C Head

Reputation: 8
  • View blog
  • Posts: 22
  • Joined: 24-February 10

Re: Little help (duplicate count and display without sorting array)

Posted 03 July 2010 - 03:23 AM

Hello... a little help again... :D...i have an array with 5000+ elements inside named idNo[]... i did a duplicate count (displays on how many times the element is displayed and what is the element dplicated) and my problem is, if the duplicate count is more than 2, it prints like:

Duplicates of 2103044 appears in the array: 2
Duplicates of 2103044 appears in the array: 3

or

Duplicates of 2096269 appears in the array: 2
Duplicates of 2096269 appears in the array: 3
Duplicates of 2096269 appears in the array: 4

I wanted to just display like "Duplicates of 2103044 appears in the array: 3" instead of printing 2 lines. and vice versa.

code is here:

	int duplicateCounter = 1;
   		
		for (int i = 0; i < idNo.length; i++ ) {
		   duplicateCounter = 1;
			for (int j = i + 1; j < idNo.length; j++){
				if(idNo[j] == idNo[i]){	
					duplicateCounter++;
					System.out.println("Duplicates of " + idNo[i]  + " appears in the array: " + duplicateCounter);
				}	
			}
			
		}



Thanks people!!
Was This Post Helpful? 0
  • +
  • -

#11 Luckless   User is offline

  • </luck>
  • member icon

Reputation: 293
  • View blog
  • Posts: 1,146
  • Joined: 31-August 09

Re: Little help (duplicate count and display without sorting array)

Posted 03 July 2010 - 07:12 AM

you just need to move where you put the print statement:

int duplicateCounter = 1;
  		
	for (int i = 0; i < idNo.length; i++ ) {
	   duplicateCounter = 1;
		for (int j = i + 1; j < idNo.length; j++){
			if(idNo[j] == idNo[i]){	
				duplicateCounter++;
			
			}	
		}
        System.out.println("Duplicates of " + idNo[i]  + " appears in the array: " + duplicateCounter);
		
	}




The reason I move it from inside your second for loop to the outside of it is because you only want to print once AFTER you have searched the entire array for duplicates. Also, you might want to set your duplicateCounter to 0 instead of 1 on the off-chance that there isn't any of one number. Let the for loop verify that there is. Happy Coding :bigsmile:
Was This Post Helpful? 0
  • +
  • -

#12 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12302
  • View blog
  • Posts: 45,400
  • Joined: 27-December 08

Re: Little help (duplicate count and display without sorting array)

Posted 03 July 2010 - 02:00 PM

Duplicate topics merged. This is the third duplicate topic you have opened. Please stop duplicate posting.

Also, what is wrong with the solution I offered?

This post has been edited by macosxnerd101: 03 July 2010 - 02:02 PM

Was This Post Helpful? 0
  • +
  • -

#13 pbl   User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8378
  • View blog
  • Posts: 31,956
  • Joined: 06-March 08

Re: Little help (duplicate count and display without sorting array)

Posted 03 July 2010 - 08:33 PM

The stupid brute force using an array of boolean to register if it was done or not

public class Duplicate {

	public static void main(String[] arg) {
		int[] array = {1, 3, 5, 6, 2, 3, 6, 4, 3, 2, 1, 6, 3};
		
		displayDuplicate(array);
		
	}
	
	static void displayDuplicate(int[] ar) {
		boolean[] done = new boolean[ar.length];
		for(int i = 0; i < ar.length; i++) {
			if(done[i])
				continue;
			int nb = 0;
			for(int j = i; j < ar.length; j++) {
				if(done[j])
					continue;
				if(ar[j] == ar[i]) {
					done[j] = true;
					nb++;
				}
			}
			System.out.println(ar[i] + " occurs " + nb + " times");
		}
	}
}


Was This Post Helpful? 0
  • +
  • -

#14 joms999   User is offline

  • New D.I.C Head

Reputation: 8
  • View blog
  • Posts: 22
  • Joined: 24-February 10

Re: Little help (duplicate count and display without sorting array)

Posted 06 July 2010 - 06:17 AM

View Postpbl, on 03 July 2010 - 07:33 PM, said:

The stupid brute force using an array of boolean to register if it was done or not

public class Duplicate {

	public static void main(String[] arg) {
		int[] array = {1, 3, 5, 6, 2, 3, 6, 4, 3, 2, 1, 6, 3};
		
		displayDuplicate(array);
		
	}
	
	static void displayDuplicate(int[] ar) {
		boolean[] done = new boolean[ar.length];
		for(int i = 0; i < ar.length; i++) {
			if(done[i])
				continue;
			int nb = 0;
			for(int j = i; j < ar.length; j++) {
				if(done[j])
					continue;
				if(ar[j] == ar[i]) {
					done[j] = true;
					nb++;
				}
			}
			System.out.println(ar[i] + " occurs " + nb + " times");
		}
	}
}



At last someone helped me.. and got the correct output..
Sir Thank you, but one favor, could you put comments on the program to explain the flow... :D... sorry but I'm not used to boolean... now I've learned that I should study more about boolean... :D

Thanks again sir
Was This Post Helpful? 0
  • +
  • -

#15 pbl   User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8378
  • View blog
  • Posts: 31,956
  • Joined: 06-March 08

Re: Little help (duplicate count and display without sorting array)

Posted 06 July 2010 - 03:45 PM

public class Duplicate {

	public static void main(String[] arg) {
		// array for testing
		int[] array = {1, 3, 5, 6, 2, 3, 6, 4, 3, 2, 1, 6, 3};
		// call the method that display the results
		displayDuplicate(array);
		
	}
	// receive the array to display as parameter
	static void displayDuplicate(int[] ar) {
		// build an array of boolean the same size as the array to display
		boolean[] done = new boolean[ar.length];
		
		// pass through the array
		for(int i = 0; i < ar.length; i++) {
			// if this value has already by processed pass to the next one
			if(done[i])
				continue;
			// counter for the number of occurence of this new value
			int nb = 0;
			// scan from our actual position to the end of the array
			for(int j = i; j < ar.length; j++) {
				// if this value has already been processed go check next ar[j]
				if(done[j])
					continue;
				// if both are equal
				if(ar[j] == ar[i]) {
					done[j] = true;     // flag this value as having been processed
					nb++; 				// increment the counter for this value
				}
			}
			// display the count for ar[i]
			System.out.println(ar[i] + " occurs " + nb + " times");
		}
	}
}


Was This Post Helpful? 1
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2