LeetCode 219 414

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() == 3return 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() == 3return 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 > 0return result[2];  // 仍有空闲的位置,说明不存在第三大的数
40        else return result[0];
41    }
42}

留下评论

您的电子邮箱地址不会被公开。 必填项已用*标注