287. 寻找重复数

题目描述 给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。 示例 1: 输入: [1,3,4,2,2] 输出: 2 示例 2: 输入: [3,1,3,4,2] 输出: 3 说明: 不能更改原数组(假设数组是只读的)。 只能使用额外的 O(1) 的空间。 时间复杂度小于 O(n2) 。 数组中只有一个重复的数字,但它可能不止重复出现一次。 https://leetcode-cn.com/problems/find-the-duplicate-number/ 解法1 首先,题目说了不能更改数组、且空间复杂度为O(1),那么我们就不能够使用排序算法。此外,时间复杂度要求小于O(n^2),就不能够使用暴力法(双重循环遍历每个元素)。 题目描述了有n+1个元素,值域为[1, n],这就提示我们:我们可以用数组内容作为数组的索引。例如nums = [1,3,4,2,2]: 索引 0 1 2 3 4内容 1 3 4 2 2从索引为0开始,使用数组内容作为索引遍历:nums[0] = 1nums[1] = 3nums[3] = 2nums[2] = 4nums[4] = 2nums[2]…

Read more