c - 如何检查字符数组c中的重复项

Question

我对 C 还很陌生，如何检查一维字符数组的重复项

例如

#define MAX_SIZE 60
Char canvas[MAX_SIZE] = {0};
for(int i=0; i<MAX_SIZE;i++){
   //How do i check if there is a duplicate in that array?
}

如何迭代以检查重复项，例如我是否必须使用双 for 循环并在此处执行 sizeOf(canavas)/SOMETHING 操作？

Answer 1

我的解决方案，使用函数:

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>

bool mem_hasduplicates(const char arr[], size_t len)
{
    assert(arr != NULL);
    if (len == 0) 
        return false;
    for (size_t i = 0; i < len - 1; ++i) {
        for (size_t j = i + 1; j < len; ++j) { 
            if (arr[i] == arr[j]) { 
                return true;
            }
        }
    }
    return false;
}

int main() {
    const char canvas[] = "zcxabca";
    printf("%x\n", mem_hasduplicates(canvas, sizeof(canvas)/sizeof(canvas[0])));


    const char other_canvas[] = "abcfsd";
    printf("%x\n", mem_hasduplicates(other_canvas, sizeof(other_canvas)/sizeof(other_canvas[0])));
}

实时版本可在 onlinegdb 获取.

@edit 或者我们可以按照 @selbie 的建议“仅”从所有数字创建一个直方图，尽管这让我很快变得复杂:

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>

struct histogram_value_s {
    char value;
    unsigned int count;
};

struct histogram_s {
    struct histogram_value_s *v;
    size_t len;
};


#define HISTOGRAM_INIT()  {0}

void histogram_fini(struct histogram_s *t)
{
    t->len = 0;
    free(t->v);
}

static int histogram_sort_by_value_qsort_cb(const void *a0, const void *b0)
{
    const struct histogram_value_s *a = a0;
    const struct histogram_value_s *b = b0;
    assert(a != NULL);
    assert(b != NULL);
    return a->value - b->value;
}

void histogram_sort_by_value(struct histogram_s *t)
{
    qsort(t->v, t->len, sizeof(*t->v), histogram_sort_by_value_qsort_cb);
}

static int histogram_sort_by_count_qsort_cb(const void *a0, const void *b0)
{
    const struct histogram_value_s *a = a0;
    const struct histogram_value_s *b = b0;
    assert(a != NULL);
    assert(b != NULL);
    return a->count - b->count;
}

void histogram_sort_by_count(struct histogram_s *t)
{
    qsort(t->v, t->len, sizeof(*t->v), histogram_sort_by_count_qsort_cb);
}


int histogram_getValue_2(const struct histogram_s *t, char value, size_t *idx, unsigned int *ret0)
{
    for (size_t i = 0; i < t->len; ++i) {
        if (t->v[i].value == value) {
            if (ret0) {
                *ret0 = t->v[i].count;
            }
            if (idx) {
                *idx = i;
            }
            return 0;
        }
    }
    return -1;
}

void histogram_printlns_generic(const struct histogram_s *t, const char fmt[])
{
    assert(t != NULL);
    for (size_t i = 0; i < t->len; ++i) {
        printf(fmt, t->v[i].value, t->v[i].count);
    }
}

int histogram_add(struct histogram_s *t, char value)
{
    size_t idx;
    if (histogram_getValue_2(t, value, &idx, NULL) == 0) {
        if (t->v[idx].count == UINT_MAX) {
            goto ERR;
        }
        ++t->v[idx].count;
    } else {
        void *tmp;

        tmp = realloc(t->v, (t->len + 1) * sizeof(*t->v));
        if (tmp == NULL) goto ERR;
        t->v = tmp;

        t->v[t->len] = (struct histogram_value_s){
            .value = value,
            .count = 1,
        };
        ++t->len;
    }

    return 0;
ERR:
    return -1;
}

bool histogram_has_any_count_greater_then_2(const struct histogram_s *t)
{
    assert(t != NULL);
    for (size_t i = 0; i < t->len; ++i) {
        if (t->v[i].count >= 2) {
            return true;
        }
    }
    return false;
}

/* ----------------------------------------------------------- */

int histogram_create_from_mem(struct histogram_s *ret0, const char arr[], size_t len)
{
    assert(ret0 != NULL);
    assert(arr != NULL);

    struct histogram_s ret = HISTOGRAM_INIT();

    for (size_t i = 0; i < len; ++i) {

        const char to_add = arr[i];

        if (histogram_add(&ret, to_add) < 0) {
            goto ERR;
        }
    }

    *ret0 = ret;
    return 0;
ERR:
    histogram_fini(&ret);
    return -1;
}

int main() {
    const char canvas[] = "abc";

    struct histogram_s h;
    int ret;
    ret = histogram_create_from_mem(&h, canvas, sizeof(canvas)/sizeof(canvas[0]));
    if (ret) {
        fprintf(stderr, "mem_createhistogram error!\n");
        return -1;
    }


    printf("'%s' %s duplicates\n",
        canvas,
        histogram_has_any_count_greater_then_2(&h)
            ? "has"
            : "does not have"
    );

    histogram_fini(&h);
}

直播版here .

@edit 或者我们可以对数组进行排序，并检查任意两个相邻字节是否相同!

#include <stdlib.h>
#include <stdbool.h>

int cmp_chars(const void *a, const void *b)
{
    return *(char*)a - *(char*)b;
}

int main() {
    char canvas[] = "abca";

    qsort(canvas, sizeof(canvas) - 1, sizeof(canvas[0]), cmp_chars);

    bool duplicate_found = false;
    for (char *p = canvas; p[1] != '\0'; ++p) {
        if (p[0] == p[1]) {
            duplicate_found = true;
            break;
        }
    }

    printf("'%s' %s duplicates\n",
        canvas,
        duplicate_found ? "has" : "does not have");
}

实时版本可在 onlinegdb 获取.