For example I have an array:
arr[9] = {1, 3, 4, 9, 2, 9, 2, 9, 7}
I then sort the array to get
arr[9] = {1, 2, 2, 3, 4, 7, 9, 9, 9}
Then I count duplicates for each value using two for loops. The output I want is:
2 instances of 2
3 instances of 9
Instead, I get:
2 instances of 2
3 instances of 9
2 instances of 9
I know that after the loop goes once, when arr[6], the outer loop counts that there are two more 9 but after that is finished, and loop goes to arr[7], the outer loop still counts there is another 9 which is arr[8]. So my question, how do I stop the code when it has counted duplicates for each number in the array once. Thanks!
Example code:
#define NUM = 9
int main() {
arr[NUM] = {1, 3, 4, 9, 2, 9, 2, 9, 7};
sort_int_array(arr, NUM); //insertion sort function
int i, j, count=1;
for (i=0; i<NUM; i ) {
for (j=i 1;j<NUM; j ) {
if (arr[i] == arr[j]) {
count ;
}
if (arr[i] != arr[j] && count>1) {
printf("%d instances of %d\n", count, arr[i]);
count=1;
}
}
}
}
CodePudding user response:
I found the answer guys, thank you for helping. I just needed to remove the 2nd for loop.
#define NUM = 9
int main() {
arr[NUM] = {1, 3, 4, 9, 2, 9, 2, 9, 7};
sort_int_array(arr, NUM); //insertion sort function
int i, count=1;
for (i=0; i<NUM; i ) {
if (arr[i] == arr[i 1]) {
count ;
}
if (arr[i] != arr[i 1] && count>1) {
printf("%d instances of %d\n", count, arr[i]);
count=1;
}
}
}
CodePudding user response:
I think the problem is you go to the first nine, then it counts the next two. THEN it will go to the duplicate and also compare the duplicate against the other duplicate. I assume what you could do is check if arr[i] is not equal to arr[i - 1] so you don't compare duplicates
CodePudding user response:
Here is a demonstrative program that shows how numbers of occurrences of elements of an array cam be calculated.
#include <stdio.h>
#include <stdlib.h>
int cmp( const void *a, const void *b )
{
int x = *( const int * )a;
int y = *( const int * )b;
return ( y < x ) - ( x < y );
}
int main(void)
{
int arr[] = {1, 3, 4, 9, 2, 9, 2, 9, 7};
const size_t N = sizeof( arr ) / sizeof( *arr );
qsort( arr, N, sizeof( int ), cmp );
for ( size_t i = 0; i != N; )
{
size_t j = i;
size_t count = 1;
while ( i != N && arr[i] == arr[j] ) count;
printf( "%zu instances of %d\n", count, arr[j] );
}
return 0;
}
The program output is
1 instances of 1
2 instances of 2
1 instances of 3
1 instances of 4
1 instances of 7
3 instances of 9
If you want you may substitute this call of printf
printf( "%zu instances of %d\n", count, arr[j] );
for this one
if ( count != 1 ) printf( "%zu instances of %d\n", count, arr[j] );
In this case the output will be
2 instances of 2
3 instances of 9
EDIT: As for your solution published as an answer to your own question then the code invokes undefined behavior due to accessing memory beyond the array in this expression arr[i 1]
when i
is equal to NUM - 1
for (i=0; i<NUM; i ) {
if (arr[i] == arr[i 1]) {
^^^^^^^^
count ;
}
if (arr[i] != arr[i 1] && count>1) {
^^^^^^^^
printf("%d instances of %d\n", count, arr[i]);
count=1;
}
}
CodePudding user response:
You don't need to use two for loops for this, it would be inefficient and increases the complexity of the code.
If you are doing this with hand you would
- Bring another sheet of paper.
- for each number in the array:
- if it's the first time you see this number:
Note it down and record it has count of 1 - else:
then increment the count by 1
- if it's the first time you see this number:
if you only need elements that occurred at least twice, you can filter out elements with count = 1.
As for the code:
// this is called frequency array, which we will use to store the
// number of occurrences (frequency) of a given number.
// The size of the array must be larger than the largest number in the array
int sz = 10 // sz = largest expected element 1 (this only works for array of integers).
int freq[sz];
memset(freq, 0, sz * sizeof(int)); // reset all values in the array to 0
int arr[9] = {1, 2, 2, 3, 4, 7, 9, 9, 9};
int i;
for (i = 0;i < 9;i ){
cur = arr[i]; // read the current element
freq[cur] = 1; // increment its count by 1
}
for (i = 0;i < sz;i ) {
count = freq[i]; // read the count of the number i
if(count != 0) {
// a count of 0 means that the number didn't occur in the array
// you can also exclude numbers occurring only once by count > 1
printf("%d instances of %d\n", count, i);
}
}
I didn't test this code but this is the concept, you can find more here.
This implementation uses more space than needed, but it has fast access time, if you move to cpp, you can use stl map
or unordered_map
for more space-efficient solution.