LeetCode 219 414

个人思路参考

LeetCode 219 414

题219 确定指定长度内是否存在重复值(参考讨论区)

Given 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

代码:

class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        // 使用滑动窗口 side window,每次检查滑动窗口内部是否包含新进入窗口的数字
        Set<Integer> set = new HashSet<Integer>();
        for (int i=0; i<nums.length; i++) {
            if (i > k) set.remove(nums[i-k-1]);
            if (!set.add(nums[i])) return true;
        }
        return false;
    }
}

题 414 查找第三大的元素

Given 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

class Solution {
    public int thirdMax(int[] nums) {
        Arrays.sort(nums);  // 完全排好序

        Set<Integer> last = new HashSet<Integer>();  // 查找第三大的数,重复的不算
        int result = nums[nums.length-1];

        for (int i=nums.length-1; i>=0 && last.size()<3; i--) {
            if (last.add(nums[i])) {
                result = nums[i];
            }
        }

        if (last.size() == 3) return result;
        else return nums[nums.length-1];
    }
}

第二种思路

Runtime: 4 ms, Memory Usage: 37.3 MB

我用的选择排序,至少遍历三次数组,堆排序没有试了

class Solution {
    public int thirdMax(int[] nums) {
        int ceiling = 3;
        for (int i=0; i<ceiling && i<nums.length; i++) {
            int maxi = i;
            for (int j=i+1; j<nums.length; j++) {
                if (nums[j] > nums[maxi]) maxi = j;
            }

            if (i>0 && nums[maxi] == nums[i-1]) ceiling += 1;  //出现相同的数据,遍历的次数需要增加

            int t = nums[i];
            nums[i] = nums[maxi];
            nums[maxi] = t;

        }

        //System.out.println(Arrays.toString(nums));

        Set<Integer> front = new HashSet<>();
        int result = 0;
        for (int j=0; front.size()<3 && j<nums.length; j++) {

            if (front.add(nums[j])) result = nums[j];
        }
        if (front.size() == 3) return result;
        else return nums[0];
    }
}

第三种思路

遍历一次数组,每次保证 result 数组里存储的是前三大的数

Runtime: 1 ms, Memory Usage: 36.4 MB

class Solution {
    public int thirdMax(int[] nums) {
        int [] result = new int[3];
        int free = 3;  // result 空闲的位置数量

        result[0] = result[1] = result[2] = 0;
        for (int i=0; i<nums.length; i++) {
            // System.out.println(Arrays.toString(result));
            if (free == 3) {  // 临时填充当前元素作为最大值
                result[2] = nums[i];
                free -= 1;
            }
            else if (nums[i] > result[2]) {  // 更新最大值
                result[0] = result[1];
                result[1] = result[2];
                result[2] = nums[i];
                free -= 1;
            }
            else if (nums[i] < result[2]) {  // 第二大的数候选
                if (free == 2) {  // 临时填充当前元素作为第二大的数
                    result[1] = nums[i];
                    free -= 1;
                }
                else if (nums[i] > result[1]) {  // 更新第二大的数
                    result[0] = result[1];
                    result[1] = nums[i];
                }
                else if (nums[i] < result[1]) {  // 第三大的数候选
                    // System.out.println(nums[i]);
                    if (free == 1) {  // 临时填充当前元素作为第三大的数
                        result[0] = nums[i];
                        free -= 1;
                    }
                    else if (nums[i] > result[0])  // 更新第三大的数
                        result[0] = nums[i];
                }
            }
        }
        if (free > 0) return result[2];  // 仍有空闲的位置,说明不存在第三大的数
        else return result[0];
    }
}

发表评论

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