剑指刷题1

发表于 | 分类于 ，

一.面试题3：数组中重复的数字

题目：在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

解题思路：所有的题目都是冲着复杂度越小越好的目标去的，所以空间复杂度就应该是O（1），而时间复杂度就应该是O（n）。这题本身就有点可以投巧的点，就是长度为n，而且所有数字都在0～n-1的范围内，所以在没有重复数字的情况下，应该是数组的每个下标都与它对应的值相等。因此下面的算法思路就是遍历整个数组，尽量让所有的数都在其应该的位置（即下标值等于对应值），而实现这一步的做法就是交换两个数的位置。若发现要交换的两个数相等时，就发现了一个重复的数字了。

-*- coding:utf-8 -*-
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        if numbers == None or len(numbers) <= 0:
            return False
        for i in range(len(numbers)):
            if numbers[i] < 0 or numbers[i] > len(numbers)-1:
                return False
        for i in range(len(numbers)):
            while numbers[i] != i :
                if numbers[i] == numbers[numbers[i]]:
                    duplication[0] = numbers[i]
                    return True
                a = numbers[i]
                numbers[i] = numbers[a]
                numbers[a] = a
        return False

代码思路：首先排除一些异常的情况，也就是前面两段：排除输入的数组为空以及数组长度等于或小于零的情况，排除数组的值超出限定范围的情况。然后就是主体部分，直接遍历整个数组，这里就不多赘述啦，看解题思路。

——————————————————————————————————————————————————

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

题目：给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

解题思路：这一题有两种做法，一种是二分法， 另一种是快慢指针。我这里先讲讲快慢指针的做法吧，感觉这个做法挺常看到的。尤其是在数组这类题中。快慢指针的做法里面有一个很关键的概念：环。

要理解快慢指针的问题的话，有几个关键的问题需要理解：1.slow和fast为什么会在环中相遇时，多走的n步满足n%c==0? 2.为什么finder和slow相遇在入口？

回答：1.首先假设，起点到环的入口长度为m，环的周长为c，在fast和slow相遇时slow走了n步。则fast走了2n步，fast比slow多走了n步。首先走的n步是m+（在环上走的长度），剩余的n步就是一直在绕圈了，所以才会得出那个结论。2.fast和slow相遇时，slow在环中行进的距离是n-m，其中n%c==0。这时我们再让slow前进m步——也就是在环中走了n步了（此时finder也走了m步，到了环的入口）。而n%c==0即slow在环里面走的距离是环的周长的整数倍，就回到了环的入口了，而入口就是重复的数字。

Solution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def findDuplicate(self, nums: List[int]) -> int:
    slow=0
    fast=0
    while(1):
        slow=nums[slow]
        fast=nums[nums[fast]]
        if(slow==fast):
            break
    find=0
    while(1):
        find=nums[find]
        slow=nums[slow]
        if(find==slow):
            return find

代码思路：首先第一个循环是找出fast和slow相遇的位置，然后第二个循环是找出环的入口位置。注：这里没有写特殊情况的处理，可能是测试的例子里面没有包括吧，在leetcode跑过了。在第一个循环中要注意，循环条件是不能写成while slow != fast 的因为初始条件是slow==fast=0的，所以两个指针就启动不了了。

注：这两题的前提假设都是不同的，如果使用第二小题的思路去解第一小题的话会出现问题，因为环在开始的时候就出现了，这就直接默认了数组第一个是重复数字，但显然这个结论是错误的。

请作者喝杯咖啡吧！