算法——找出数组中唯一重复的值

95 阅读 0 评论 63 点赞

我是靠谱客的博主贪玩音响，最近开发中收集的这篇文章主要介绍算法——找出数组中唯一重复的值，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

条件数组是无序的。区分数组内的数值是否有范围

一、数组内的值没有限制时

最简单的方法：空间换取时间

时间复杂度O(n^2)，空间复杂度O(n)

class Solution:
    def FindDup(self, arr):
        if not arr:
            return
        wind = []
        n = len(arr)
        for i in range(n):
            if arr[i] not in wind:
                wind.append(arr[i])
            else:
                return arr[i]
        return

二、当数组内的值限定为 1到 n时：

首先，什么是异或？？？相同为0，不同为1。

如：10^6 =？转换成二进制，

10- 0000 1010

6- 0000 0110 对应bit异或得到： 0000 1100 即12

1、利用异或的方法：

自己本身异或 = 0， 0和任何数异或 = 任何数本身。

利用2次遍历得到重复数。

举例： arr = [1, 3, 2, 4, 2]

得到 0到4的异或(0^1^2^3^4)结果 A，再和数组中的每个数异或

(0^1^2^3^4) ^(1^3^2^4^2) = 1^1^2^2^2^3^3^4^4 = 2

class Solution:
    def FindDup(self, arr):
        if not arr:
            return
        n = len(arr)
        x = 0
        for i in range(n):
            x ^= i
            x ^= arr[i]
        return x

2、求数组和的方法。

由于限定数组值为1到n-1，arr = [1, 3, 2, 4, 2] 的数值范围为1到4 , 即1+2+3+4=10

数组内和为 1+3+2+4+2= 12，相差的值即为唯一重复值2

class Solution:
    def FindDup(self, arr):
        if not arr:
            return
        n = len(arr)
        sum1, sum2 = 0, 0
        for i in range(n):
            sum1 += i
            sum2 += arr[i]
        return sum2-sum1

相似的题目：

删除排序数组中的重复项

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2],

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。

你不需要考虑数组中超出新长度后面的元素。

class Solution:
    def DeleteDup(self, arr):
        if not arr:
            return
        n = len(arr)
        #双指针法
        p, q = 0, 1
        while q<n:
            #注意该题目是建立在数组已经排序的基础上，所以重复项放一起
            if arr[p] == arr[q]:
            #快慢指针相等时后移
                q += 1
                continue
            #将不重复的赋到p+1位置
            arr[p+1] = arr[q]
            p += 1
            q += 1
        return len(arr[:p+1])

移除指定值的所有元素：

O(1)的空间，删除掉数组中值= val的所有元素并返回。

示例：输入 arr=[3, 2, 2, 3] val = 3 输出 arr=[2, 2]

一样使用双指针：

class Solution:
    def DeleteEle(self, arr, val):
        if not arr:
            return
        n = len(arr)
        p, q = -1, 0
        while q<n:
            if arr[q] == val:
                q += 1
                continue
            arr[p+1] = arr[q]
            p += 1
            q += 1
        return arr[:p+1]