剑指Offer的学习笔记（C#篇）-- 数组中重复的数字
题目描述
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
一 . 解题思路
方法一：效率低的方法。
给数组搞内外两个循环，第一个循环是把数组的每一个数都遍历出来，而第二个循环是，除了第一个数组正在遍历的那个数以外的数进行查找，找到和他一样的，就结束，不一样，再继续，文字表述太抽象，我都傻了，请看图！！（按照1-2-3-4一直循环就行），但是效率低。
代码实现：
class Solution { public bool duplicate(int[] numbers, int[] duplication) { //数组遍历 for(int i = 0; i < numbers.Length; i++) { //抛去遍历数组的第一个数后，开始遍历，寻找相同的那个数 for(int j = i + 1; j < numbers.Length; j++) { //如果相同，则输出 if(numbers[i]==numbers[j]) { duplication[0]=numbers[i]; return true; } } } //如果没有，则返回false return false; } }
方法二：搞一个队列
先看图：
啥意思呢：就是建一个队列，遍历一遍，如果队列里有重复的数，停止；没有的话，继续搞，用到一个.Contains。
代码实现：
using System.Collections.Generic; class Solution { public bool duplicate(int[] numbers, int[] duplication) { // write code here //为0时的判断 if(numbers.Length==0) return false; //建个队列 Queue<int> que=new Queue<int>(); //循环 for(int i=0;i<numbers.Length;i++) { //队列里有的话，duplication[0]=numbers[i];返回ture if(que.Contains(numbers[i])) { duplication[0]=numbers[i]; return true; } //否则，把这个数加到队列里 else { que.Enqueue(numbers[i]); } } return false; } }