-
October 19th, 2009, 11:23 PM
#1
Array Duplicates
Hi everyone, I'm new and will probably be asking a lot of questions from here on out. I have an assignment where the user inputs 10 integers into an array, then the program is supposed to output the numbers, but no duplicates. (ex. INPUT: 1 2 2 3 1 10 6 4 6 20 OUTPUT: 1 2 3 10 6 4 20)
What I'm having trouble with is figuring out the algorithm needed to not cout the duplicates.
Here's what I have...
Code:
#include <iostream>
using namespace std;
int main()
{
int num[10];
cout << "Enter 10 numbers...\n";
for(int i=0; i<10;i++)
cin >> num[i];
And that's where I'm at. We are also not allowed to sort the array. I wanted to try something like
Code:
int n=0;
for(int j=0; j<10;j++)
{
if(num[n] != num[n+1]
cout << num[i]
n++;
}
but since it isn't sorted, it will not check any previous numbers in the array, only the one next to it...
-
October 19th, 2009, 11:29 PM
#2
Re: Array Duplicates
Using an unordered_set (from TR1 or Boost) would fit the no-sorting requirement, but is probably not what the teacher had in mind.
A naive solution would use two nested loops: The first would iterate over every entered element, and the second would check to see if that element exists earlier in the array. That would do it; however, it's going to be far less efficient than a sorting-based approach.
If there's a relatively small maximum value which could be entered, you could use an array of bools to record whether you've seen a given value yet. Obviously this won't work too well if you have to handle negatives or all possible integers up to 2^32-1.
-
October 19th, 2009, 11:44 PM
#3
Re: Array Duplicates
Yes she did mention using two nested for loops. I'm having trouble with creating the algorithm in the 2nd for loop to check for duplicates. I can only really think of the way to do it if it was sorted.
-
October 20th, 2009, 02:33 AM
#4
Re: Array Duplicates
If it isn't to be sorted then you need some way of remembering the numbers that you have already come across. You could use a vector for this.
What I'm thinking is that create a 'memory' vector, every number you read in, you check to see if it is in the 'memory' vector, if not, you add it to your 'memory' vector and print the value to the display, else you do nothing and a carry on to the next value.
-
October 20th, 2009, 02:54 AM
#5
Re: Array Duplicates
http://www.cplusplus.com/reference/algorithm/remove/
This should help. I doubt your teacher wants you to use this algorithm, but you can use its loop code.
Simply start at index 0, and remove all numbers equal to num[0] in index 1 to 10. Repeat at index 1, 2 etc...
Just remember that as you remove numbers, your array gets smaller.
-
October 20th, 2009, 03:09 AM
#6
Re: Array Duplicates
We can't use vectors (haven't learned them just yet) or remove the value from the array (asked not to, but this looks nice), only accepted way she was asking for was two for loops. I think I'm getting there though.
Code:
#include <iostream>
using namespace std;
int main()
{
int num[10];
bool is_dup = true;
cout << "Enter 10 numbers..." <<endl;
for (int i=0; i<10; i++)
{
cin >> num[i];
}
for (int j=0; j<10;j++) //repeats 10 times
{
for (int k=j; k>=0; k--) //this will repeat from j to 0
{
if (num[j] != num[k]) //checks if one number isn't equal to others below it
is_dup = false;
}
if (is_dup == false)
}
return 0;
}
I didn't finish it just yet. I just wanted to know if I'm making progress towards the right direction, and if what I'm doing makes sense.
-
October 20th, 2009, 03:19 AM
#7
Re: Array Duplicates
The direction is right.
You just have to set is_dup to false before the inner loop and set is_dup to true if the inner and outher value match.
btw the inner loop should be
Code:
for (int k=j-1; k>=0; k--)
to optimize the soluton a little you could break the inner loop when a duplicate was found
Kurt
-
October 20th, 2009, 03:35 AM
#8
Re: Array Duplicates
Originally Posted by viperlasson
We can't use vectors (haven't learned them just yet) or remove the value from the array (asked not to, but this looks nice), only accepted way she was asking for was two for loops. I think I'm getting there though.
Code:
#include <iostream>
using namespace std;
int main()
{
int num[10];
bool is_dup = true;
cout << "Enter 10 numbers..." <<endl;
for (int i=0; i<10; i++)
{
cin >> num[i];
}
for (int j=0; j<10;j++) //repeats 10 times
{
for (int k=j; k>=0; k--) //this will repeat from j to 0
{
if (num[j] != num[k]) //checks if one number isn't equal to others below it
is_dup = false;
}
if (is_dup == false)
}
return 0;
}
I didn't finish it just yet. I just wanted to know if I'm making progress towards the right direction, and if what I'm doing makes sense.
When you say "Cannot remove the value from the array", what exactly are you supposed to do? print them out as you find numbers, but only if they aren't duplicates?
In this case, yeah, I guess you are in the right direction. Although I would say your check is inverted. Also, you need to start the loop at j-1, or you will test the number against itself.
Code:
is_dup = false;
for (int k=j-1; k>=0; k--) //this will repeat from j-1 to 0
{
if (num[j] == num[k]) //checks if one number is equal to others below it
is_dup = true; //You found a duplicate.
}
if (is_dup == false) //No duplicates detected
//do something
else
//do nothing
-
October 21st, 2009, 12:52 AM
#9
Re: Array Duplicates
Got it working, thanks for your help.
Here is my code
Code:
#include <iostream>
using namespace std;
int main()
{
int num[10];
bool is_dup;
cout << "Enter 10 numbers..." <<endl;
for (int i=0; i<10; i++)
{
cin >> num[i];
}
for (int j=0; j<10;j++)
{
is_dup= false;
for (int k=j+1; k<10; k++) //this will repeat from j-1 to 0
{
if (num[j] == num[k]) //checks if one number is equal to others below it
is_dup = true; //You found a duplicate
}
if (is_dup == false)
cout << num[j] << " ";
}
cout << endl;
return 0;
}
edit: woops didnt really change some of my comments...
Last edited by viperlasson; October 21st, 2009 at 12:57 AM.
-
November 2nd, 2009, 04:31 AM
#10
Re: Array Duplicates
Originally Posted by viperlasson
Got it working,
Does it really work?
Say you have the same number three times in the array. You find the number and look for duplicates. You'll find two duplicates. But then you'll find the number again and this time it has one duplicate.
So how do you know if a number has already been counted as duplicate?
..X......X..........X........
When you encounter any number, say X, you must first check so there are no X to the left. If there are, the X is already accounted for as duplicate and should be skipped.
Last edited by nuzzle; November 2nd, 2009 at 04:54 AM.
-
November 2nd, 2009, 07:39 AM
#11
Re: Array Duplicates
Originally Posted by nuzzle
Does it really work?
Say you have the same number three times in the array. You find the number and look for duplicates. You'll find two duplicates. But then you'll find the number again and this time it has one duplicate.
So how do you know if a number has already been counted as duplicate?
..X......X..........X........
When you encounter any number, say X, you must first check so there are no X to the left. If there are, the X is already accounted for as duplicate and should be skipped.
I agree with nuzzle. However, by now, I believe your program is too complicated. You should invest in writing helper functions:
I would recommend these two functions:
Code:
bool isFirstOccurrence()
int countOccurrences()
If you know how to use iterators, I recommend this interface:
Code:
bool isFirstOccurrence(int* begin, int* end, int* valuePosition)
int countOccurrences(int* begin, int* end, int value)
else, use this one:
Code:
bool isFirstOccurrence(int array[], int size, int valueIndex)
int countOccurrences(int array[], int size, int value)
or even better, just use the corresponding std::algorithm
with these two functions, this is what your code will look like:
PHP Code:
bool isFirstOccurrence(int array[], int size, int valueIndex); //Prototype int countOccurrences(int array[], int size, int value); //Prototype
int main() { static const int SIZE = 10;
int num[SIZE]; cout << "Enter 10 numbers..." <<endl; for (int i=0; i<SIZE; i++) { cin >> num[i]; }
for (int i=0; i<SIZE; i++) //repeats 10 times { if (isFirstOccurrence(num, SIZE, i) == true) { int occurrences = countOccurrences(num, SIZE, num[i]); if (occurrences == 1) { cout << num[i] << " appears only once." << endl; } else { cout << num[i] << " appears " << occurrences << " times." << endl; } } //else do nothing } return 0; }
bool isFirstOccurrence(int array[], int size, int valueIndex) { //Write the actuall implementation }
int countOccurrences(int array[], int size, int value) { //Write the actuall implementation }
By doing this, not only is your code MUCH clearer, but the odds of you accidently leaving a bug in there gets much smaller too.
-
November 2nd, 2009, 10:55 AM
#12
Re: Array Duplicates
Originally Posted by monarch_dodra
By doing this, not only is your code MUCH clearer, but the odds of you accidently leaving a bug in there gets much smaller too.
I agree in general but it's not that complicated. It's just two nested loops and a counter,
Code:
for (int i=0; i<SIZE; i++) {
int n = num[i]; // a number
int c = 0; // counter
for (int j=0; j<SIZE; j++) {
if (num[j] == n]) { // an occurance
if (j<i) break; // already accounted for - skip
else c++; // count
}
}
if (c>0) { // not skipped
// c holds total number of occurrences of n
}
}
-
November 2nd, 2009, 11:17 AM
#13
Re: Array Duplicates
Originally Posted by nuzzle
I agree in general but it's not that complicated. It's just two nested loops and a counter.
Nice. Your code does have the advantage of being more efficient (no separate iteration for checking uniqueness and counting).
The code isn't rocket science, that's for sure, but I feel it goes against the "don't write write-only code". While I'm sure writing the code is easy, it takes a little bit of concentration to figure out what it really does, especially if you have no idea what it is supposed to do to begin with.
-
November 1st, 2009, 07:44 PM
#14
Re: Array Duplicates
Bumping my thread for an updated version of this program. Now I need to not display any duplicates and count how many times a number was present in the array. It seems simple, but I can't understand where to reset the counter variable.
Code:
#include <iostream>
using namespace std;
const int SIZE = 3;
int test[SIZE];
int counter=1;
bool is_dup;
int main()
{
cout << "Enter three test grades: ";
for (int i=0; i < SIZE; i++)
cin >> test[i];
for (int j=0; j<SIZE; j++)
{
is_dup = false;
for(int k=j+1; k<SIZE; k++)
{
if(test[j] == test[k])
{
is_dup=true;
counter++; //this counts all the duplicates...
}
}
if (is_dup == false)
{
cout << test[j] << " " << counter << "\n\n";
//EDIT-ADDED counter=1;
}
}
return 0;
}
I have my counter in there, but I need to reset it back to one after it finishes counting duplicates of a number. Don't know if I am doing this right so far.
edit: Okay I'm solving it little by little, I just made it reset the counter after it prints the number + times it appeared, makes sense... Just now theres an issue where if you type in (1 1 1) it says it counts 4 duplicates in the array.
I also have another question... I made my program to use an array of only 3 numbers. What if the user enters as many as they want, then a certain number to quit and print results? I know a while loop will be needed, but how will I increase the array size each time the user enters a test score?
Last edited by viperlasson; November 1st, 2009 at 08:16 PM.
-
November 2nd, 2009, 03:20 AM
#15
Re: Array Duplicates
Originally Posted by viperlasson
Bumping my thread for an updated version of this program. Now I need to not display any duplicates and count how many times a number was present in the array. It seems simple, but I can't understand where to reset the counter variable.
I have my counter in there, but I need to reset it back to one after it finishes counting duplicates of a number. Don't know if I am doing this right so far.
edit: Okay I'm solving it little by little, I just made it reset the counter after it prints the number + times it appeared, makes sense... Just now theres an issue where if you type in (1 1 1) it says it counts 4 duplicates in the array.
I also have another question... I made my program to use an array of only 3 numbers. What if the user enters as many as they want, then a certain number to quit and print results? I know a while loop will be needed, but how will I increase the array size each time the user enters a test score?
Start your counter at 0, not 1.
For your last question, you have two option:
The bad one: Create an array with 1000 elements. Fill it in as the user goes, and remember how many items he has put it.
The good one: Use a vector.
I know your not supposed to use them, but really, if that is what you want to do, you don't have much of an option.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|