Repetition of elements

1

I am having difficulty outputting the number of elements repeated in the vector. Here is the code:

#include <stdio.h>
#include<stdlib.h>

int main()
{
    int N, i, temp, repetidos = 1;

    int *v1;

    printf ("Entre com N: ");
    scanf ("%d", &N);

    v1 = (int *)malloc(N * sizeof (int));

    temp = v1[0];

    for (i=1; i < M + 1; ++i){
        scanf ("%d", &v1[i]);

        if (v1[i] == temp){
            repetidos++;

            if (repetidos > 1){
                printf ("%d", repetidos);
            }
            temp = v1[i];
        }               
    }
}
    
asked by anonymous 07.11.2016 / 22:32

3 answers

2

If I understand you, you want the number of numbers that are repeated in the vector. Example: {1, 2, 3, 3, 3} must return that 1 number repeats (the 3). The vector {1, 3, 3, 2, 1, 4, 4, 5} should return four, since four values are repeated in vector (1, 2, 3 and 4).

In your case, it was not clear if the vector is ordered. So I implemented quick sort to do this, which makes solving the problem a lot easier.

Furthermore, it was not clear whether the original vector could be modified. For this reason, I created a copy of it ( v2 ) and ordered it. The repeticoesNumero variable is getting the number of times a value appears in the vector. If this value is greater than one, it means that the value repeats, and thus increments the variable resposta , which at the end of execution will have the number of elements that are repeated in the vector. Below the code:

#include <stdio.h>
#include <stdlib.h>
void quickSort(int a[], int l, int r) {
    int j;

    if(l < r)  {
        j = partition( a, l, r);
        quickSort(a, l, j-1);
        quickSort(a, j+1, r);
    }
}

int partition(int a[], int l, int r) {
    int pivot, i, j, t;
    pivot = a[l];
    i = l;
    j = r+1;

    while(1) {
        do
            ++i;
        while(a[i] <= pivot && i <= r);
        do
            --j;
        while(a[j] > pivot);
        if( i >= j ) break;
        t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    t = a[l];
    a[l] = a[j];
    a[j] = t;
    return j;
}
int main() {
    int n, i, temp, repeticoesNumero, resposta = 0;
    int *v1, *v2;

    printf ("Entre com n: ");
    scanf ("%d", &n);

    v1 = (int *)malloc(n * sizeof (int));
    v2 = (int *)malloc(n * sizeof (int));

    for(i = 0; i < n; ++i) {
        scanf("%d", &v1[i]);
        v2[i] = v1[i];
    }

    quickSort(v2, 0, n - 1);

    temp = v2[0];
    repeticoesNumero = 1;

    for (i = 1; i < n; i++) {
        if (v2[i] == temp) repeticoesNumero++;
        else {
            if (repeticoesNumero > 1) resposta++;
            temp = v2[i];
            repeticoesNumero = 1;
        }
    }
    if (repeticoesNumero > 1) resposta++;
    printf("%i numero(s) se repete(m) no vetor.\n", resposta);
}

Hope this is it!

Just a note : In your code there is a M in the for loop. I believe it was just a typo and the original value is N . My implementation is considering it to be a typo.

    
08.11.2016 / 00:50
1

I will make a code as simple as it gives a beginner who does not know and can not do more complex things. In a professional code would be quite different, there would be functions, a data structure suitable for this, probably with bits and other optimizations.

I would not do with sorting because of the cost and complexity of the implementation.

As I said in the comments I would need an auxiliary vector to indicate if there is repetition. I hope the requirements are correct, I did according to what I understood.

#include <stdio.h>
#include <stdlib.h>

int main() {
    int N, repetidos = 0;
    printf("Entre com N: ");
    scanf("%d", &N);
    int *v1 = malloc(N * sizeof (int));
    int *aux = malloc(N * sizeof (int));
    int *flag = malloc(N * sizeof (int));
    int cont = 0;
    for (int i = 0; i < N; i++) {
        scanf ("%d", &v1[i]);
        int achou = 0;
        for (int j = 0; j < cont; j++) {
            if (v1[i] == aux[j]) {
                flag[j] = 1;
                achou = 1;
                break;
            }
        }
        if (!achou) {
            aux[cont] = v1[i];
            flag[cont++] = 0;
        }
    }
    for (int i = 0; i < cont; i++) {
        repetidos += flag[i];
    }
    if (repetidos > 0) {
        printf ("\n%d repetidos", repetidos);
    }
}

See running on ideone and on CodingGround .

If you can discard the vector you can simplify it a bit:

#include <stdio.h>
#include <stdlib.h>

int main() {
    int N, repetidos = 0;
    printf("Entre com N: ");
    scanf("%d", &N);
    int *v1 = malloc(N * sizeof (int));
    int *flag = malloc(N * sizeof (int));
    int cont = 0;
    for (int i = 0; i < N; i++) {
        int valor = 0;
        scanf ("%d", &valor);
        int achou = 0;
        for (int j = 0; j < cont; j++) {
            if (valor == v1[j]) {
                flag[j] = 1;
                achou = 1;
                break;
            }
        }
        if (!achou) {
            v1[cont] = valor;
            flag[cont++] = 0;
        }
    }
    for (int i = 0; i < cont; i++) {
        repetidos += flag[i];
    }
    if (repetidos > 0) {
        printf ("\n%d repetidos", repetidos);
    }
}

See working on ideone and on CodingGround .

    
08.11.2016 / 01:10
0

To find the number of repeats, there are a few options:

  • Use a Boolean vector that is also N-sized to store houses visited. For each house of the original vector, search the remaining houses for repeated searches. If you find them, enter the positions in the boolean and increment the repeat count (only once). While continuing the search, ignore the homes you have visited.

  • Or, sort the vector. So just sweep it and see if there are adjacent houses alike. If so, increase the counter and continue to the next unrepeatated house.

08.11.2016 / 00:21