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

找出数组中重复元素

程序员文章站 2023-12-27 18:23:39
...

题目描述

一个大小为n的数组,里面的数都属于范围[0, n-1],有不确定的重复元素,找到至少一个重复元素;
要求O(1)空间和O(n)时间;

方法1

因为数组长度为n,且数的范围为[0~n-1],且包含重复元素,故将数组中的每个元素置位到和坐标值相同的位置,0->0,1->1,2->2,以此类推,如果存在重复元素,则必然会使某两个位置上的元素值相同。

int find_rongyu(vector<int> res){
    if (res.size() <= 1)return 0;
    for (int i = 0; i < res.size(); i++){
        while (i != res[i]){
            if (res[i] == res[res[i]])return res[i];
            swap(res[i], res[res[i]]);
        }
    }
    return 0;
}

方法2

对以数组元素值为下标的数组元素值加上n。
将数组中的某个元素值res[i]作为下标,若res[res[i]] >= n时,则判断已经进行过加法运算,此下标为重复元素值。否则,对res[res[i]]+=n处理;

int find_rongyu1(vector<int> res){
    if (res.size() <= 1)return 0;
    int n = res.size();
    for (int i = 0; i < n; i++){
        if (res[i] >= n){
            return i;
        }
        res[res[i]] += n;
    }
    return 0;
}

方法3

可以将此问题看作是一个“判断单链表是否存在环,若存在找出环”的问题。
单链表采用数组实现,每个元素值作为next指针,指向下一个元素,可以将问题转化为“已知一个单链表存在环,找出环的入口点”。
思路:将res[i]看做是第 i 个元素的索引,即res[i] -> res[res[i]]-> res[res[res[i]]]…最终形成一个单链表,由于数组存在重复元素,则一定存在一个环,且环的入口点就是重复元素。

int find_rongyu2(vector<int> res){
    if (res.size() <= 1)return 0;
    int x, y;
    x = y = 0;
    do{
        x = res[res[x]];
        y = res[y];
    } while (x != y);
    x = 0;
    do{
        x = res[x];
        y = res[y];
    } while (x != y);
    return x;
}
相关标签: 重复元素

上一篇:

下一篇: