剑指 Offer 03. 数组中重复的数字

标签：重复   bre   list   oid   util   hashset   测试用例   个数   imp   

package com.example.lettcode.offer;

import java.util.*;

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

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

 * 限制：
 * 2 

// 解法1：利用List，时间复杂度超时
public static int findRepeatNumber(int[] nums) {
	List integerList = new ArrayList();
	for (int i = 0; i 

// 解法2：利用Set
public static int findRepeatNumber(int[] nums) {
	Set set = new HashSet();
	int repeat = -1;
	for (int num : nums) {
		if (!set.add(num)) {
			repeat = num;
			break;
		}
	}
	return repeat;
}

// 解法3：题目中提到长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。构建一个等长的数组，只要num[i]为下标的元素的值不为0，就说明曾经出现过
// 时间复杂度和空间复杂度均为O(n)
public static int findRepeatNumber(int[] nums) {
	int[] temp = new int[nums.length];
	for (int i = 0; i 

// 测试用例
public static void main(String[] args) {
	int[] nums = new int[]{2, 3, 1, 0, 2, 5, 3};
	int ans = findRepeatNumber(nums);
	System.out.println("demo01 result:" + ans);
        // leetcode上有个测试用例长度在10K左右，容易超时
}

剑指 Offer 03. 数组中重复的数字

标签：重复   bre   list   oid   util   hashset   测试用例   个数   imp   

原文地址：https://www.cnblogs.com/fyusac/p/13194374.html