算法数组中重复的数字是什么(算出数组中重复的值)

导语：算法：数组中重复的数字

题目：

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

2 <= n <= 100000

示例：

输入：[2, 3, 1, 0, 2, 5, 3]输出：2 或 3 

思路：

简单的方法是用map记录出现的数，如果后面数在map中出现了，则返回该数。

更好的方法：因为数组大小是n，数组元素是0-n-1，所以可以把元素映射到索引上，索引对应的位置的值加n(目的：1.标记该索引出现过；2.通过取模操作获取该索引未修改的值)。这样，遍历过程中，如果发现索引对应元素的值大于n，说明之前访问过，也就是重复元素。

代码：

class Solution {public:    int findRepeatNumber(vector<int>& nums) {        int n=nums.size();        for(auto& val: nums)        {            int idx = val%n;            if(nums[idx] < n)            {                nums[idx] += n;            }else                return idx;        }        return -1;    }};

免责声明:本站部份内容由优秀作者和原创用户编辑投稿，本站仅提供存储服务，不拥有所有权,不承担法律责任。若涉嫌侵权/违法的，请反馈，一经查实立刻删除内容。本文内容由快快网络小涵创作整理编辑！