p287

发表于 | 分类于 |

LeetCode 287 Find the Duplicate Number 题解

1.题目：

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

题意：

输入一个数组，长度为n+1,里面的数的范围为1~n,所有总会有一个数重复，找出那个数 。（重复次数可能不止一次）

2.解题思路:

桶装

3.代码

[title] [] [url] [link text]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 

public class Solution {
    public int findDuplicate(int[] nums) {
       int ans=0;
		int len = nums.length;
		int[] list = new int[len];
		for (int i=0;i<len;i++)
		{
			list[nums[i]]++;
			if (list[nums[i]]>1)
				return nums[i];
		}
		
		return ans;
    }
}

4.一些总结：