【牛客 - 剑指offer】JZ3 数组中重复的数字 两种思路 Java实现

---

剑指offer题解汇总 Java实现

https://blog.csdn.net/guliguliguliguli/article/details/126089434

本题链接

https://www.nowcoder.com/exam/oj/ta?difficulty=2&page=1&pageSize=50&search=&tpId=13&type=265

题目

思路 & 代码

① 使用HashSet判断是否有重复的数字

set集合中只能存放不同的内容，所以：

1. 先创建一个HashSet集合

2. 向set中添加数据之前，先判断set中是否已经包含该数字

   • 如果set中已经包含该数字，则把该数字返回，程序结束

   • 如果set中没有包含该数字，则把该数字添加到set中，循环继续

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param numbers int整型一维数组
     * @return int整型
     */
    public int duplicate(int[] numbers) {
        // write code here

        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < numbers.length; i++) {
            if (set.contains(numbers[i])){
                return numbers[i];
            }
            set.add(numbers[i]);
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

② 位置重排

在题目中提到在一个长度为n的数组里的所有数字都在0到n-1的范围内，如果不存在重复的数字，那么0 ~ n-1 的每一个数都会出现一次，把它们按照从小到大的顺序排序的话，数组中的值和它的索引值是一样的。

1. 遍历数组

• 如果当前值和索引值一样，则说明该数字就在正确的位置上，continue（跳过这一次的循环）

• 如果当前值和索引值不一样

  • 检查以该值为索引的对应的值（即numbers[numbers[i]]）是否和当前值（numbers[i]）相等

    • 如果相等，则找到了重复的值，将该值返回即可

    • 如果不相等，则交换numbers[numbers[i]]和numbers[i]的位置

    交换的意义在于，让numbers[i]的值和索引值一样，比如，n=5，numbers[0] = 3，则把3这个值放在numbers[3]的位置，也就是交换numbers[0]和numbers[3]

2. 遍历能够顺利结束，说明没有重复的值，并且每个数字都应经在正确的位置上

所谓“正确”，就是numbers[i]=i

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param numbers int整型一维数组
     * @return int整型
     */
    public int duplicate(int[] numbers) {
        // write code here
        for (int i = 0; i < numbers.length; i++) {

            //这个数就在它的位置上
            if (numbers[i] == i) {
                continue;
            }
            //这个数不在它的位置上
            //数组中以numbers[i]的值为索引的数组的值 是否等于 numbers[i]
            if (numbers[i] == numbers[numbers[i]]) {
                return numbers[i];
            } else {
                swap(numbers, i, numbers[i]);
            }
        }
        return -1;
    }

    private void swap(int[] numbers, int index1, int index2) {
        int temp = numbers[index1];
        numbers[index1] = numbers[index2];
        numbers[index2] = temp;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34