Leetcode 每日一题:1692. 按键持续时间最长的键

自己的思路

使用 哈希法 ,将字符映射到数组的索引中,然后在遍历的时候记录最大值。

最后通过两个循环找到合适下标

第一个循环找到出现次数最大的值

第二个循环根据这个最大值找到下标。由于要找到按照字符排序大小输出了答案,所以需要逆序查找

时间复杂度 O(3N),空间复杂度 O(1)

class Solution {
    public char slowestKey(int[] releaseTimes, String keysPressed) {
        int[] map = new int[26];
        Arrays.fill(map, 0);
        int index = keysPressed.charAt(0) - 'a';

        map[index] = releaseTimes[0];
        for (int i = 1; i < keysPressed.length(); i++) {
            index = keysPressed.charAt(i) - 'a';
            map[index] = Math.max(map[index], releaseTimes[i] - releaseTimes[i - 1]);
        }
  
        int max = 0;
        int maxIndex = 0;
        for (int i = 0; i < map.length; i++) {
            if (max < map[i]) {
                max = map[i];
            }  
        }
        for (int i = map.length - 1; i >= 0; i--) {
            if (map[i] == max) {
                maxIndex = i;
                break;
            }
        }

        return (char)(maxIndex + 'a');

    }
}

哈希法 不一定非得用 Map 集合 ,能使用数组的就使用数组,因为数组本来就是哈希法最基础的实现工具。

我看到我自己实现的哈希算法,在整体速度上排第三。后面的都是使用 HashMap 来做的。

别人的思路

和自己的差不多,但是可以对我的算法进行优化。时间复杂度压缩到 O(N),将我额外的两个循环的判断逻辑放到了第一个循环上,实现效率上的提升。

class Solution {
    public char slowestKey(int[] releaseTimes, String keysPressed) {
        int time = releaseTimes[0];
        char res = keysPressed.charAt(0);
        for (int i = 1; i < keysPressed.length(); i++) {
            int cur = releaseTimes[i] - releaseTimes[i - 1];
            if (time < cur || (time == cur && res < keysPressed.charAt(i))) {
                time = cur;
                res = keysPressed.charAt(i);
            }
        }

        return res;
    }
}

这样看,优化过后的算法就是一个 贪心算法。不断取最大值,获取当前的局部最优,最后得到全局最优。

  • LeetCode

    LeetCode(力扣)是一个全球极客挚爱的高质量技术成长平台,想要学习和提升专业能力从这里开始,充足技术干货等你来啃,轻松拿下 Dream Offer!

    209 引用 • 72 回帖
  • 每日一题
    8 引用 • 4 回帖
  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3011 引用 • 8158 回帖 • 549 关注

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...