Sword_Offer 数组中重复的数字[3]

Sword_Offer 数组中重复的数字[3]

题目一：找出数组中重复的数字

0x00 题目描述

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

0x01 解题思路

#!/usr/bin/env python3
# -*- coding:utf-8 -*-
# Author LQ6H

class Solution:
    def duplicate(self,arr):
        """
        :param arr: List[int]
        :return: int
        """
        if not arr:
            return

        n=len(arr)
        res=0

        for i in range(n):
            if arr[i]<0 or arr[i]>n-1:
                return

        for i in range(n):
            while arr[i]!=i:

                if arr[i]==arr[arr[i]]:
                    res=arr[i]
                    return res

                index=arr[i]
                arr[i]=arr[index]
                arr[index]=index

        return False

0x02 性能分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

0x03 测试用例

• 1.长度为n的数组里包含一个或多个重复的数字
• 2.数组中不包含重复的数字
• 3.输入空列表或n之外的数字

题目二：不修改数组找出重复的数字

0x00 题目描述

题目与上面类似,长度为n+1的数组里的所有数字都在1~n的范围内,唯一要求数组不能修改

0x01 解题思路

#!/usr/bin/env python3
# -*- coding:utf-8 -*-
# Author LQ6H

class Solution:
    def getDuplication(self,arr):
        """
        :param arr: List[int]
        :return: int
        """
        if not arr:
            return -1

        start=1
        end=len(arr)-1

        while end>=start:
            middle=((end-start)>>1)+start
            count=self.countRange(arr,start,middle)

            if end==start:
                if count>1:
                    return start
                else:
                    break

            if count>(middle-start+1):
                end=middle
            else:
                start=middle+1

        return -1

    def countRange(self,arr,start,end):
        count=0

        for i in range(len(arr)):
            if arr[i]>=start and arr[i]<=end:
                count+=1

        return count

0x02 性能分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)