找出重复的数

[编程题]找出重复的数

热度指数：2089 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

在包含 n+1 个数的序列 a 中找出重复的数。序列 a 中包含从 1 到 n 的整数，且只有一个数有重复值。
要求时间复杂度为 O(n)，额外空间复杂度为 O(1)。

示例1

输入

4,[1,2,1,4,3]

输出

备注:

其中1<=n<=100000。
要求时间复杂度为O(n)，额外空间复杂度为O(1)

算法知识视频讲解

two倩

/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param n int
* @param a int一维数组
* @param aLen int a数组长度
* @return int

使用异或：1，1，2，3，4和1，2，3，4的异或结果就是重复的值

int search(int n, int* a, int aLen ) {
int i=0;
for(int s=0;s<aLen;s++)
i^=a[s]^s;
return i;
}

发表于 2021-09-09 22:22:37 回复(0)

Python

Pukino

class Solution:
    def search(self , n , a ):
        # write code here
        return sum(a) - ((n + 1) * n // 2)

发表于 2021-06-15 20:35:17 回复(0)

Python

spongebob7

return sum(a)-((n+1)*n/2)

发表于 2021-03-26 14:21:45 回复(1)

C++

牛客594675055号

class Solution {public:        int search(int n, vector<int>& a) {                for (int i = 0; i < a.size(); i++)        {            if (a[abs(a[i]) - 1] < 0)            {                return abs(a[i]);            }            else            {                a[abs(a[i]) - 1] = -a[abs(a[i]) - 1];            }        }        return -1;    }};

发表于 2022-01-16 18:21:12 回复(0)

Java

banana程序猿

这个题目那里说了求和的事了？

发表于 2021-11-28 19:50:58 回复(0)

喝口锟斤拷，疾呼烫烫烫

谁能告诉我n有什么用

func search( n int ,  a []int ) int {
    m:=make(map[int]bool)
    for _,v:=range a{
        if _,ok:=m[v];ok{
            return v
        }else {
            m[v]=true
        }
    }
    return 0
}

发表于 2021-06-05 11:36:22 回复(0)

Phinks

int search(int n, vector<int>& a) {
        // write code here
        int target;
        for(int i = 0; i <= n; ) {
            if(a[i] == i)
                i++;
            else if(a[a[i]] == a[i]) {
                target = a[i];
                break;
            }
            else {
                int temp = a[a[i]];
                a[a[i]] = a[i];
                a[i] = temp;
            }
        }
        return target;
    }

发表于 2021-03-21 16:02:26 回复(3)

Qiumg

public int search (int n, int[] a) {
        // write code here
        HashSet<Integer> set = new HashSet<>();
        for(int i=0;i<n+1;i++){
            if(!set.add(a[i])){
                return a[i];
            }
        }
        return 0;
    }

发表于 2021-03-08 17:20:48 回复(3)