594. 最长和谐子序列

内容

和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1。

现在,给定一个整数数组,你需要在所有可能的子序列中找到最长的和谐子序列的长度。

示例 1:

输入: [1,3,2,2,5,2,3,7]
输出: 5
原因: 最长的和谐数组是:[3,2,2,2,3].
说明: 输入的数组长度最大不超过20,000.


思路

既然子序列中最大值和最小值差别为1,那么就是说,这两个元素处于排序后数组中的相邻位置,所以这里先对数组排序。
然后将这些元素出现的次数存储起来用对象表示。
最后依次统计相邻元素里出现次数最多的值,也就是最大子序列的长度。


代码

/**
最长和谐子序列

思路,既然子序列中最大值和最小值差别为1,那么就是说,这两个元素处于排序后数组中的相邻位置,所以这里先对数组排序。
然后将这些元素出现的次数存储起来用对象表示。
最后依次统计相邻元素里出现次数最多的值,也就是最大子序列的长度。
 * @param {number[]} nums
 * @return {number}
 */
var findLHS = function (nums) {
    var map = {};

    nums.sort(function (a, b) {
        return a - b;
    })

    nums.forEach(function (item) {
        if (map[item] == null) {
            map[item] = 1;
        } else {
            map[item] += 1;
        }
    })

    var keys = Object.keys(map);
    var maxLength = 0;
    for (var i = 0; i < keys.length; i++) {
        var nowKey = keys[i];
        var nextKey = keys[i + 1];
        var nowVal = map[nowKey];
        var nextVal = map[nextKey];

        if (Math.abs(nextKey - nowKey) == 1 && nowVal + nextVal > maxLength) {
            maxLength = nowVal + nextVal;
        }
    }

    return maxLength;
};

回到目录

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 概述:排序有内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部...
    每天刷两次牙阅读 3,747评论 0 15
  • 1.基于ijkplayer封装的开源框架GiraffePlayer播放器,如果想在同一个播放界面进行多个视频切换播...
    小婷android阅读 131评论 0 0
  • 昨日与一个美女闲聊一小时,颇有感触。 这位美女有多美呢,作为外貌协会天秤座的我,也觉得她的美是值得围观的。 18岁...
    梅凉阅读 683评论 27 11
  • 学习这么久还是能量不稳定,遇到孩子不听话的时候又开始焦虑了。翻开日记本,看到语音课瑞连的分享记录,心情又好了许多。...
    浅笑嫣然love阅读 173评论 2 2
  • 脑袋空白一片,试图在短时间内扫描几篇文章,以找寻写字的灵感。 一旦有时间的紧迫感,我很难吸收文章的信息,何况不是我...
    Aga阅读 439评论 0 2