欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

查找数组中重复的元素

程序员文章站 2022-07-12 09:28:15
...

数组a共n+1个元素,元素取值范围1~n,返回数组中重复的元素之一

题目条件限定了数组中一定有重复元素,可以对每个可能的取值1~n计算出现次数。或者划分取值范围为1~m,m+1~n,计算两个取值区间在数组a中出现的总次数,如果范围为1~m的统计次数大于m,说明有重复。但如果有某个符合取值范围的元素数组中出现了0次,那么可能为某个重复次数为两次的元素提供了隐蔽条件,这个重复的元素也无法找出,但说明另一个取值范围内也有元素是重复的

int cntRange(int* a, int len, int st, int end) {
    int cnt = 0;
    for (int i = 0; i < len; i++) {
        if (a[i] <= end && a[i] >= st)cnt++;
    }
    return cnt;
}
int func(int* a, int len) {
    int st = 1, end = len - 1, mid, cnt;
    while (st <= end) {
        mid = (st + end) / 2;
        cnt = cntRange(a, len, st, mid);
        if (st == end) {
            if (cnt > 1)return st;
            else return -1;
        }
        if (cnt > mid - st + 1)end = mid;
        else st = mid + 1;
    }
}

void test02() {
    //int a1[] = { 49,38,65,97,76,13,27,49 };
    int a[] = { 2,3,5,4,4,2,6,7 };
    //for (const int i : a)cout << i << ' '; cout << endl;
    cout << func(a, sizeof(a) / sizeof(*a)) << endl;
}

 

相关标签: 算法 算法