剑指Offer算法题——数组中重复的数字（JAVA）

83 阅读 0 评论 55 点赞

我是靠谱客的博主落寞煎饼，最近开发中收集的这篇文章主要介绍剑指Offer算法题——数组中重复的数字（JAVA），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目描述：找出数组中重复的数字。

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

示例 1：

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

首先我们复习一下相关的数据结构知识：

Set

1.概述和特点

Java.util包 Interface Set<E> extends Collection<E>

特点：Set集合不包含重复元素的集合；没有带索引的方法，所以不能使用普通for循坏遍历。

HashSet对迭代对象的顺序不作任何保证

哈希值：

①是JDK根据对象的地址或者字符串或数字算出来的int类型的数值

不是对象的地址值

②Object类中有一个方法可以获取对象的哈希值

Public int hashCode() 返回对象的哈希码值

同一次对象多次调用hashCode()方法返回的哈希值是相同的

默认情况下，不同对象的哈希值是不相同的。（通过方法重写，可以实现不同对象的哈希值是相同的）

2.HashSet

Java.util Class HashSet<E> extends AbstractSet<E> implements Set<E>

实现Set接口，由哈希表支持

①特点：

1）底层数据结构是哈希表

2）对集合的迭代顺序不作任何保证，也就是说不保证存储和取出的元素顺序一致

3）没有带索引的方法，所以不能使用普通for循环遍历（可以迭代器和增强for遍历）

4）由于是Set集合，所以是不包含重复元素的集合

思路与题解：

我们利用哈希表（Set）来记录数组的各个数组，将数字每个元素挨个遍历一遍，放入一个新数组中，当查找到重复数组则返回此数组。

算法流程：

①初始化HashSet，记为dic

②遍历数组中每个数字：

当遍历到一个存在与dic中的数字时，说明重复，就返回此数字

再将此数字添加到dic中

③返回-1

代码：

class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> dic = new HashSet<>();
        for(int num : nums) {//增强的for循坏
            if(dic.contains(num)) return num;
            dic.add(num);
        }
        return -1;
    }
}