Найти уникальное значение в массиве. C

Question

В программе формирую массив, который выгдяит примерно так: types [1,1,2,3,4,5,5,5,1,1]. Мне нужно найти и вывести уникальные значения, для данного примера: 1,2,3,4,5. То есть вернее будет выразиться - вывести все встречающиеся значения. Как это можно реализовать в С?

Answer 1

Если не особо заморачиваться и решать в лоб, то вот простейший алгоритм с квадратичной сложностью. Суть - бежим по основному массиву, и каждого кандидата проверяем, нет ли его ещё в списке, если нет - добавляем. Я не заморачивался с перевыделением памяти - просто завел максимально возможный массив.

#include <stdio.h>

int main()
{
    #define size 10
    int a[size] = {1,1,2,3,4,5,5,5,1,1};
    int b[size] = {0};
    int found = 0;
    for (int i = 0; i < size; i++) {
        int c = 0;
        for (int j = 0; j < found; j++) {
            if (a[i] == b[j]) { c = 1; break;}
        }
        if (c == 0) { b[found] = a[i]; found++;}
    }
    printf("found = %d\n", found);
    for (int i = 0; i < found; i++) {
        printf("%d ", b[i]);
    }
    puts("");
}

Если массив можно сортировать, тогда это можно сделать за n*log n

#include <stdio.h>
#include <stdlib.h>
// с этим компаратором нужно быть аккуратным:)
int compare (const void * a, const void * b)
{
  return ( *(int*)a - *(int*)b );
}

int main()
{
    #define size 10
    int a[size] = {1,1,2,3,4,5,5,5,1,1};
    qsort(a, size, sizeof(a[0]), compare);

    int c = a[0];
    printf("%3d", c);
    for (int i = 1; i<size; i++) {
        if (a[i] != c) {
            c = a[i];
            printf("%3d", c);
        }
    }
    puts("");
}

в этом случае даже нет второго массива - можно сразу выводить.

Если же известен диапазон значений, то можно и линейно сделать

#include <stdio.h>
#include <memory.h>
int main()
{
    #define size 10
    int a[size] = {1,1,2,3,4,5,5,5,1,1};
    // 1000 - это максимальное значение, которое может быть в исходном массива (да, на самом деле 999, но мы все знаем +-1)
    #define BUF_SIZE 1000
    int buf[BUF_SIZE] = {0};
    memset(buf, 0, BUF_SIZE*sizeof(a[0]));

    for (int i = 0; i < size; i++) {
        buf[a[i]] = 1;
    }
    for (int i = 0; i < BUF_SIZE; i++) {
        if (buf[i] > 0) {
            printf("%3d", i);
        }
    }
    puts("");
}

Answer 2

Ну, тогда покажу и я свое решение, раз дали квадратичное :)

int cmp(const void *a_, const void *b_)
{
    int a = *(int*)a_;
    int b = *(int*)b_;
    return a < b ? -1 : a > b ? 1 : 0;
}

int main()
{
    int a[] = {1,1,2,18,43,14,3,4,5,5,5,1,1};

    qsort(a,sizeof(a)/sizeof(a[0]),sizeof(int),cmp);

    printf("%d ",a[0]);
    for(int i = 1; i < sizeof(a)/sizeof(a[0]); ++i)
        if (a[i] != a[i-1]) printf("%d ",a[i]);
}

Для такого маленького диапазона 0-0xFF проще будет

int main()
{
    int a[] = {1,1,2,18,43,14,3,4,5,5,5,1,1};
    int b[256] = { 0 };
    for(int i = 0; i < sizeof(a)/sizeof(a[0]); ++i)
        if (b[a[i]] == 0) b[a[i]]++;
    for(int i = 0; i < 256; ++i)
        if (b[i]) printf("%d ",i);
}

БЛОГ НА HUSL

Найти уникальное значение в массиве. C

Ответы (2 шт):