链接
https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/
难度: #简单
题目
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1:
输入:
[2, 3, 1, 0, 2, 5, 3]
输出:2 或 3
限制:
2 <= n <= 100000
代码框架
class Solution {
public int findRepeatNumber(int[] nums) {
}
}
题目解析
解答思路1:
暴力解法,轮询数组,
把数组的每一个数字都和后面的数字进行比较。
解答思路2:
排序去重法,先排序,然后比较两个相邻的数字,
如果相同,则找到重复数字了。
解答思路3:
使用Set集合去重,查看数字是否已经在Set集合中,
如果不存在,则加入集合,如果存在,则表示该数字重复了。
解答思路4:
boolean数组记录对于index位置的数字是否存在,
即使用nums的数字作为boolean数组的索引,
对应的值false表示不存在,true表示存在,
如果存在则说明当前数字重复了。
该思路的执行用时和内存消耗表现都较好。
解答思路5:
JDK自带的Bitset位图,
使用nums的数字作为Bitset的索引,
对应的值false表示不存在,true表示存在。
JDK自带的Bitset的执行用时和内存消耗表现一般。
解答思路6:
原地排序法,使nums的索引和其索引位置保存的数字一致,
在查找替换位置的时候,
如果发现已经有一致的数字了,
则当前数字肯定是重复数字。
画图演示思路:
测试用例
package edu.yuwen.sowrd.num03.solution;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;
import edu.yuwen.sowrd.num03.sol6.Solution;
public class SolutionTest {
@Test
public void testCase1() {
Solution sol = new Solution();
int[] nums = { 2, 3, 1, 0, 2, 5, 3 };
int repeatNumber = sol.findRepeatNumber(nums);
Assertions.assertTrue(repeatNumber == 2 || repeatNumber == 3);
}
}
解答1
package edu.yuwen.sowrd.num03.sol1;
public class Solution {
public int findRepeatNumber(int[] nums) {
for (int i = 0; i < nums.length - 1; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] == nums[j]) {
return nums[i];
}
}
}
return -1;
}
}
解答2
package edu.yuwen.sowrd.num03.sol2;
import java.util.Arrays;
public class Solution {
public int findRepeatNumber(int[] nums) {
// 先排序
Arrays.sort(nums);
// 比较两个相邻的数字
for (int i = 0; i < nums.length; i++) {
if (nums[i] == nums[i + 1]) {
return nums[i];
}
}
// 没有找到重复的数字返回-1
return -1;
}
}
解答3
package edu.yuwen.sowrd.num03.sol3;
import java.util.HashSet;
import java.util.Set;
public class Solution {
public int findRepeatNumber(int[] nums) {
Set<Integer> set = new HashSet<>(nums.length);
for (int i = 0; i < nums.length; i++) {
// 查看数字是否已经在集合中
if (set.contains(nums[i])) {
return nums[i];
}
// 数字不存在,则加入集合
set.add(nums[i]);
}
return -1;
}
}
解答4 推荐
package edu.yuwen.sowrd.num03.sol4;
public class Solution {
public int findRepeatNumber(int[] nums) {
// 索引对应nums[i],对应的值false表示不存在,true表示存在
boolean[] indexes = new boolean[nums.length];
for (int i = 0; i < nums.length; i++) {
// 查看nums[i]的值,如果为true,表示重复了
if (indexes[nums[i]]) {
return nums[i];
}
// 将对应nums[i]的索引位置置位true,表示数字存在了
indexes[nums[i]] = true;
}
return -1;
}
}
解答5
package edu.yuwen.sowrd.num03.sol5;
import java.util.BitSet;
public class Solution {
public int findRepeatNumber(int[] nums) {
// 使用Bitset记录对应数字是否存在
BitSet bs = new BitSet(nums.length);
for (int i = 0; i < nums.length; i++) {
if (bs.get(nums[i])) {
return nums[i];
}
bs.set(nums[i]);
}
return -1;
}
}
解答6 推荐
package edu.yuwen.sowrd.num03.sol6;
public class Solution {
public int findRepeatNumber(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int value = nums[i];
// 检查当前位置是否已经排序好的位置
// 否则把value放到对应的位置
// 把对应位置的数据保存到点前位置
// 即交换两者,直到本该排序好
while (i != value) {
// 先保存要被替换掉位置的数字到当前节点
nums[i] = nums[value];
// 判断要替换的位置是否已经排好,已经排好代表有重复
if (nums[value] == value) {
return value;
} else {
// 替换掉对应位置的值
nums[value] = value;
}
// 再更新当前的位置的值
value = nums[i];
}
}
return -1;
}
}
网友评论