剑指offer:数组中重复的数字

发布时间:2020-06-25 18:01:14 作者:Jayce_SYSU
来源:网络 阅读:348

题目描述:
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是第一个重复的数字2。

# -*- coding: utf-8 -*-
# @Time         : 2019-04-15 17:31
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : duplicate_num_in_array.py
# @Blog         : https://blog.51cto.com/jayce1111
# @Github       : https://github.com/SysuJayce

class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # 完整的做法是先进行输入合法性检查,然后将每个数字放到它应该在的下标,在每次交换之前先检查该下标是否已保存了正确的数字,
        # 如果是则该数字是一个重复数字
        # 时间复杂度O(n),空间复杂度O(1)。由于每个数字最多交换两次就可以放到正确的位置(第一次被从不正确的位置换到另一个不正确的位置,
        # 然后第二次就会专门为它找到属于它的位置,因此最多是两次),也就是最多比较2n次,即时间复杂度是O(n)
        if not numbers:
            return False
        if max(numbers) >= len(numbers) or min(numbers) < 0:
            return False

        for i in range(len(numbers)):
            while numbers[i] != i:
                if numbers[numbers[i]] == numbers[i]:
                    duplication[0] = numbers[i]
                    return True
                else:
                    # 注意这样交换会出现问题,需要先保存一个中间结果,不能直接交换,
                    # 否则当处理numbers[numbers[i]]的时候会找不到正确的下标
                    # numbers[i], numbers[numbers[i]] = numbers[numbers[i]], numbers[i]
                    temp = numbers[i]
                    numbers[i] = numbers[numbers[i]]
                    numbers[temp] = temp

        return False

    def duplicate2(self, numbers, duplication):
        # duplicate1()需要对输入数组进行修改,假如要求不修改输入数组,那么可以借鉴二分查找的
        # 思想,逐步缩小重复数字所在的区间。

        # 但是这种方法不能确保找到所有重复的数字,
        # 如果counter(left, right) == right - left + 1,不能排除[left, right]有重复
        # 数字的情况,例如[2, 3, 5, 4, 3, 2, 6, 7]中,counter(1, 2) == 2,但是2其实是
        # 重复数字

        # 由于是借鉴了二分查找的思想,因此while需要循环logn次,counter需要n次运算
        # 故时间复杂度O(nlogn), 空间复杂度O(1)
        def counter(start, end):  # 统计numbers中处于[start, end]之间的数字个数
            count = 0
            for num in numbers:
                if start <= num <= end:
                    count += 1
            return count

        if not numbers:  # 输入合法性判断
            return False
        left, right = 0, len(numbers) - 1  # 初始区间为[0, n-1]
        while left <= right:
            mid = (left + right) >> 1
            cnt = counter(left, mid)
            # 需要注意这里的循环出口,如果不在循环内判断left==right的情况的话就需要在循环外面
            # 再判断一次counter(left, left) == 1
            if left == right:
                if cnt > 1:
                    duplication[0] = left
                    return True
                break
            if cnt > mid - left + 1:
                # 由于是判断了 [left, mid]是否存在重复,并不能排除mid就是重复的数字,
                # 因此right不能更新为mid - 1
                right = mid
            else:
                left = mid + 1

        return False

    def duplicate3(self, numbers, duplication):
        # 由于数组中的数字范围已定,可以通过申请一个容量为数字范围的数组然后建立哈希表进行去重
        # 时间复杂度O(n), 空间复杂度O(n)
        arr = [-1] * len(numbers)
        for num in numbers:
            if arr[num] == -1:
                arr[num] = num
            else:
                duplication[0] = num
                return True
        return False
推荐阅读:
  1. 剑指offer:数字序列中某一位的数字
  2. 剑指offer:数组中出现次数超过一半的数字

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

剑指offer 数据结构 数组中

上一篇:PHPCMS V9 按浏览次数排行调用文章

下一篇:hiveserver2和metastore service的区别和联系

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》