数组中的重复数字

替换位置，查找到a[i] == i 情况时返回结果

def use_map(numbers):
    """
    使用哈希表结构
    :param numbers:
    :return:
    """
    num_map = dict()
    for number in numbers:
        if number in num_map:
            print(number)
        else:
            num_map[number] = True

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        size = len(numbers)
        if not size:
            return False
        for i in range(size):
            if numbers[i] < 0 or numbers[i] > size - 1:
                return False
        for i in range(size):
            while numbers[i] != i:  
                if numbers[i] == numbers[numbers[i]]:
                    duplication[0] = numbers[i]
                    return True
                m = numbers[i]
                numbers[i] = numbers[m]
                numbers[m] = m
        return False

func duplicateInArray(nums []int) int {
    if nums == nil || len(nums) <= 0 {
        return -1
    }
    for j := 0; j < len(nums)-1; j++ {
        if nums[j] > len(nums)-1 || nums[j] < 0 {
            return -1
        }
    }
    for i := 0; i < len(nums)-1; i++ {
        for nums[i] != i {
            if nums[i] == nums[nums[i]] {
                return nums[i]
            } else {
                nums[i], nums[nums[i]] = nums[nums[i]], nums[i]
            }
        }
    }
    return -1
}

不修改数组，查找重复数字。类二分法

func duplicateInArray(nums []int) int {
    var middle int
    var start = 1
    var end = len(nums) - 1
    if nums == nil || len(nums) == 1 {
        return -1
    }
    for start <= end {
        middle = (end-start)/2 + start
        choose := search(nums, start, middle)
        if start == end {
            return start
        }
        if choose == 1 {
            end = middle
        } else {
            start = middle + 1
        }
    }
    return middle
}
 
func search(nums []int, start, middle int) int {
    num := 0
    for i := 0; i < len(nums); i++ {
        if nums[i] <= middle && nums[i] >= start {
            num++
        }
    }
    if num <= middle-start+1 {
        return 0
    } else {
        return 1
    }

1.非递归思路

#这个函数的作用是找到重复数组所在的区间
def reduce_inter(nums, s, b):
    mid = (s + b) // 2
    count = 0
    n=len(nums)
    for i in range(n):
        if (nums[i] >= s) and (nums[i] <= mid):
            count += 1
    if count > mid-s+1:
        return s, mid
    else:
        return mid+1, b

#找到数字
def find_repeat(nums):
    s, b = 1, len(nums)-1
    while s != b:
        s, b =reduce_inter(nums, s, b)
    return s
 

2.递归思路

def loop_search(nums, l, r):
    if l == r:
        return l
    mid = (l + r) // 2
    count = 0
    n = len(nums)
    for i in range(n):
        if (nums[i] >= l) and (nums[i] <= mid):
            count += 1
    if count > mid - l + 1:
        return loop_search(nums, l, mid)
    else:
        return loop_search(nums, mid+1, r)