LeetCode 219 414
题219 确定指定长度内是否存在重复值（参考讨论区）
1Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.
查找数组中最近的两个相同元素，若这两个元素的索引之差不超过 k，则返回 True，否则返回 False
使用长度为 k 的“滑动窗口”遍历数组，每次移动窗口时检查窗口内是否存在相同元素。“窗口”使用集合 (Set) 来构造，即构造一个 Set，尝试将当前元素 nums[i] 加入集合，如果不重复就可以正常加入，接着把元素 nums[i-k] 从集合中删除；如果当前元素和集合中元素重复，就说明在距离 k 之内存在相同的元素，直接结束程序返回 True。当数组遍历完成之后依旧没有返回，则说明不存在满足条件的情况，返回 False
nums = [1, 2, 3, 1]，无；
nums = [1, 2, 3, 1]，无；
返回 False
nums = [1, 0, 1, 1, 4]，无；
nums = [1, 0, 1, 1, 4]，无；
nums = [1, 0, 1, 1, 4]，有；
返回 True
代码：
1class Solution {
2 public boolean containsNearbyDuplicate(int[] nums, int k) {
3 // 使用滑动窗口 side window，每次检查滑动窗口内部是否包含新进入窗口的数字
4 Set<Integer> set = new HashSet<Integer>();
5 for (int i=0; i<nums.length; i++) {
6 if (i > k) set.remove(nums[i-k-1]);
7 if (!set.add(nums[i])) return true;
8 }
9 return false;
10 }
11}
题 414 查找第三大的元素
1Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).
查找给定数组中的第三大数，如果不存在则返回最大值
这道题我想到的有三种思路
- 数组完全排序（快排、归并排、堆排序），选第三大的数
- 选择排序（或堆排序，堆排序应该更快），排三次，选第三次的结果
- 设置一个长度为 3 的数组（或三个变量），依次保存当前最大、第二大和第三大的元素
第一种思路
Runtime: 2 ms, Memory Usage: 36.7 MB
1class Solution {
2 public int thirdMax(int[] nums) {
3 Arrays.sort(nums); // 完全排好序
4
5 Set<Integer> last = new HashSet<Integer>(); // 查找第三大的数，重复的不算
6 int result = nums[nums.length-1];
7
8 for (int i=nums.length-1; i>=0 && last.size()<3; i--) {
9 if (last.add(nums[i])) {
10 result = nums[i];
11 }
12 }
13
14 if (last.size() == 3) return result;
15 else return nums[nums.length-1];
16 }
17}
第二种思路
Runtime: 4 ms, Memory Usage: 37.3 MB
我用的选择排序，至少遍历三次数组，堆排序没有试了
1class Solution {
2 public int thirdMax(int[] nums) {
3 int ceiling = 3;
4 for (int i=0; i<ceiling && i<nums.length; i++) {
5 int maxi = i;
6 for (int j=i+1; j<nums.length; j++) {
7 if (nums[j] > nums[maxi]) maxi = j;
8 }
9
10 if (i>0 && nums[maxi] == nums[i-1]) ceiling += 1; //出现相同的数据，遍历的次数需要增加
11
12 int t = nums[i];
13 nums[i] = nums[maxi];
14 nums[maxi] = t;
15
16 }
17
18 //System.out.println(Arrays.toString(nums));
19
20 Set<Integer> front = new HashSet<>();
21 int result = 0;
22 for (int j=0; front.size()<3 && j<nums.length; j++) {
23
24 if (front.add(nums[j])) result = nums[j];
25 }
26 if (front.size() == 3) return result;
27 else return nums[0];
28 }
29}
第三种思路
遍历一次数组，每次保证 result 数组里存储的是前三大的数
Runtime: 1 ms, Memory Usage: 36.4 MB
1class Solution {
2 public int thirdMax(int[] nums) {
3 int [] result = new int[3];
4 int free = 3; // result 空闲的位置数量
5
6 result[0] = result[1] = result[2] = 0;
7 for (int i=0; i<nums.length; i++) {
8 // System.out.println(Arrays.toString(result));
9 if (free == 3) { // 临时填充当前元素作为最大值
10 result[2] = nums[i];
11 free -= 1;
12 }
13 else if (nums[i] > result[2]) { // 更新最大值
14 result[0] = result[1];
15 result[1] = result[2];
16 result[2] = nums[i];
17 free -= 1;
18 }
19 else if (nums[i] < result[2]) { // 第二大的数候选
20 if (free == 2) { // 临时填充当前元素作为第二大的数
21 result[1] = nums[i];
22 free -= 1;
23 }
24 else if (nums[i] > result[1]) { // 更新第二大的数
25 result[0] = result[1];
26 result[1] = nums[i];
27 }
28 else if (nums[i] < result[1]) { // 第三大的数候选
29 // System.out.println(nums[i]);
30 if (free == 1) { // 临时填充当前元素作为第三大的数
31 result[0] = nums[i];
32 free -= 1;
33 }
34 else if (nums[i] > result[0]) // 更新第三大的数
35 result[0] = nums[i];
36 }
37 }
38 }
39 if (free > 0) return result[2]; // 仍有空闲的位置，说明不存在第三大的数
40 else return result[0];
41 }
42}