一.简介

​ 本系列是用来分享在洛谷，LeetCode的有趣的题目，使用Java编写且代码解释以注释为主。

​ 本篇涉及：双指针，哈希表，原地交换

二.题目

1. 移动零

题目描述：

​ 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

输入输出样例：

示例 1:

​ 输入: nums = [0,1,0,3,12]
​ 输出: [1,3,12,0,0]

示例 2:

​ 输入: nums = [0]
​ 输出: [0]

提示:

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

解法一：双指针

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
35
36
//AC代码
/**
 * 使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。
 * 右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。
 *
 * 注意到以下性质：
 * 左指针左边均为非零数；
 * 右指针左边直到左指针处均为零。
 * 
 * 复杂度分析：
 * 时间复杂度 O(N)
 * 空间复杂度 O(1)
 */
class Solution {
    public void moveZeroes(int[] nums) {
        //定义j为左指针
        int j = 0;
        //定义i为右指针，不断向右移动
        for (int i = 0; i < nums.length; i++) {
            //判断右指针不为零，将左右指针对应的数交换
            if (nums[i] != 0) {
                //但左右指针相等的时候，跳过判断
                if(i!=j){
                nums[j] = nums[i];
                //交换完后，将右指针置为0
                nums[i] = 0;
                }
                //左指针右移
                j++;
            }
        }
    }
}

//注意：不能将两个if判断写成：if(nums[i]!=0&&i!=j),因为当左指针j需要在右指针i不为零时+1
//可如果写成if(nums[i]!=0&&i!=j)，则当nums[i]!=0而i==j时，j不加1.

双指针补充（来源：力扣题解）：

双指针

2. 数组中的重复元素

题目描述：

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

输入输出样例：

示例 1:

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

提示:

​ 2 <= n <= 100000

解法一：哈希表 / Set

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
/**
 * 利用数据结构特点，容易想到使用哈希表（Set）记录数组的各个数字，当查找到重复数字则直接返回。
 *
 * 算法流程：
 * 初始化： 新建 HashSet ，记为 dic ；
 * 遍历数组 nums 中的每个数字 num ：
 * 当 num 在 dic 中，说明重复，直接返回 num ；
 * 将 num 添加至 dic 中；
 * 返回 -1−1 。本题中一定有重复数字，因此这里返回多少都可以。
 *
 * 复杂度分析：
 * 时间复杂度 O(N) ： 遍历数组使用 O(N) ，HashSet 添加与查找元素皆为 O(1)。
 * 空间复杂度 O(N) ： HashSet 占用 O(N) 大小的额外空间。
 */
class Solution {
    public int findRepeatNumber(int[] nums) {
        //创建哈希表
            Set<Integer> dic = new HashSet<>();
            //遍历nums
            for(int num : nums) {
                //当 num 在 dic 中，说明重复，直接返回 num
                if(dic.contains(num)) return num;
                //向哈希表中添加num
                dic.add(num);
            }
            return -1;
    }
}

解法二：原地交换

​ 题目说明尚未被充分使用，即 在一个长度为 n 的数组nums里的所有数字都在 0 ~ n-1 的范围内 。

​ 此说明含义：数组元素的索引和值是一对多的关系。

​ 因此，可遍历数组并通过交换操作，使元素的索引与值一一对应（即 nums[i] = inums[i]=i ）。

​ 因而，就能通过索引映射对应的值，起到与字典等价的作用。

Picture0.png

​ 遍历中，第一次遇到数字 xx 时，将其交换至索引 xx 处；而当第二次遇到数字 xx 时，一定有 nums[x] = xnums[x]=x ，此时即可得到一组重复数字。

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
35
36
37
/**
 * 1. 遍历数组 nums ，设索引初始值为 i = 0:
 *
 *    1. 若 nums[i] = i ： 说明此数字已在对应索引位置，无需交换，因此跳过；
 *
 *    2. 若 nums[nums[i]] = nums[i] ： 代表索引 nums[i] 处和索引 i 处的元素值都为 nums[i] ，即找到一组重复值，返回此值 nums[i]；
 *
 *    3. 否则： 交换索引为 i 和 nums[i] 的元素值，将此数字交换至对应索引位置。
 *
 * 2. 若遍历完毕尚未返回，则返回 -1 。
 *
 * 复杂度分析：
 * 时间复杂度 O(N) ： 遍历数组使用 O(N) ，每轮遍历的判断和交换操作使用 O(1) 。
 * 空间复杂度 O(1) ： 使用常数复杂度的额外空间。
 *
 */

class Solution {
    public int findRepeatNumber(int[] nums) {
        int i = 0;
        //遍历数组
        while(i < nums.length) {
            //如果索引和数字相等，跳过此次循环
            if(nums[i] == i) {
                i++;
                continue;
            }
            //当索引nums[i]和索引i对于的元素值都为nums[i]时，返回该重复值nums[i]
            if(nums[nums[i]] == nums[i]) return nums[i];
            //交换索引为 i 和 nums[i] 的元素值，将此数字交换至对应索引位置。
            int tmp = nums[i];
            nums[i] = nums[tmp];
            nums[tmp] = tmp;
        }
        return -1;
    }
}