首页 / 面试 / 面试题03. 数组中重复的数字

面试题03. 数组中重复的数字

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了面试题03. 数组中重复的数字，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含998字，纯文字阅读大概需要2分钟。

内容图文

题目：

技术分享图片

 

 

解答：

方法一：哈希

使用哈希来进行处理，当发现哈希中包含相应的元素时，则表示出现了重复的元素，则返回即可。

             1
            class
             Solution {

             2
            public
            :

             3
            int findRepeatNumber(vector<int>& nums) 
 4    {
 5         std::set<int> res;
 6 7for (int i = 0; i < nums.size(); i++)
 8        {
 9// 若包含元素, 则返回10if (res.count(nums[i]))
11            {
12return nums[i];
13            }
14else15            {
16// 若不包含元素, 则插入17                res.insert(nums[i]);
18            }
19        }
2021return -1;
22    }
23 };

 

方法二：仍然为哈希

  • 因为所有数字都在 0 ～ n-1 的范围内，其实完全可以省掉额外的空间开辟，将每个位置的数交换映射到其对应的数组下标下面，当出现新的元素与其对应的下标中的数字相等时，即为重复数字。
  • 这本质还是哈希的思想，思路 1 是使用库函数申请额外空间，思路 2 则是数组本身做哈希表，达到了节省空间的目的；
  • 此处会用到 while 循环，原因是保证交换过来的新元素位置也要正确
             1
            class
             Solution {

             2
            public
            :

             3
            int findRepeatNumber(vector<int>& nums) 
 4    {
 5//算法思路见剑指offer,P39-40 6if(nums.empty())
 7        {
 8return -1;
 9        }
1011for(int i = 0; i < nums.size(); ++i)
12        {
13while(nums[i] != i)
14            {
15if(nums[i] == nums[nums[i]])
16                {
17return nums[i];
18                }
19else20                {
21                    swap(nums[i], nums[nums[i]]);
22                }
23            }
24        }
2526return -1;
27    }
28 };

 

原文：https://www.cnblogs.com/ocpc/p/12856309.html

内容总结

以上是互联网集市为您收集整理的面试题03. 数组中重复的数字全部内容，希望文章能够帮你解决面试题03. 数组中重复的数字所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1233001.html

来源：【匿名】