LeetCode 219. 存在重复元素Ⅱ-C语言

题目描述

解题思路
先排序，再查找。

代码

struct node {
    int value;
    int index;
};
#define N 100000
struct node g[N] = { 0 };
int cmp(const void*a, const void*b) {
    const struct node*a1 = (const struct node*)a;
    const struct node*b1 = (const struct node*)b;
    if (a1->value == b1->value) {
        if (a1->index == b1->index) {
            return 0;
        } else if (a1->index < b1->index) {
            return -1;
        } else {
            return 1;
        }
    } else {
        if (a1->value < b1->value) {
            return -1;
        } else {
            return 1;
        }
    }
}
bool containsNearbyDuplicate(int* a, int n, int k)
{
    if (a == NULL || n <= 0) {
        return false;
    }
    memset(g, 0, sizeof(g));
    for (int i = 0; i < n; i++) {
        g[i].value = a[i];
        g[i].index = i;
    }
    qsort(g, n, sizeof(struct node), cmp);
    for (int i = 1; i < n; i++) {
        if (g[i].value == g[i - 1].value
            && abs(g[i].index - g[i - 1].index) <= k) {
            return true;
        }
    }
    return false;
}