C#LeetCode刷题之#594-最长和谐子序列​​​​​​​​​​​​​​(Longest Harmonious Subsequence)

C#LeetCode刷题之#594-最长和谐子序列​​​​​​​​​​​​​​(Longest Harmonious Subsequence)

问题

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

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

输入: [1,3,2,2,5,2,3,7]

输出: 5

原因: 最长的和谐数组是:[3,2,2,2,3].

说明: 输入的数组长度最大不超过20,000.

We define a harmonious array is an array where the difference between its maximum value and its minimum value is exactly 1.

Now, given an integer array, you need to find the length of its longest harmonious subsequence among all its possible subsequences.

Input: [1,3,2,2,5,2,3,7]

Output: 5

Explanation: The longest harmonious subsequence is [3,2,2,2,3].

Note: The length of the input array will not exceed 20,000.

示例

public class Program {

    public static void Main(string[] args) {
        var nums = new int[] { 1, 3, 2, 2, 5, 2, 3, 7 };

        var res = FindLHS(nums);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    public static int FindLHS(int[] nums) {
        var res = 0;
        var dic = new Dictionary<int, int>();
        for(var i = 0; i < nums.Length; i++) {
            if(dic.ContainsKey(nums[i])) {
                dic[nums[i]]++;
            } else {
                dic[nums[i]] = 1;
            }
        }
        foreach(var item in dic) {
            if(dic.ContainsKey(item.Key + 1)) {
                res = Math.Max(res, dic[item.Key + 1] + item.Value);
            }
            if(dic.ContainsKey(item.Key - 1)) {
                res = Math.Max(res, dic[item.Key - 1] + item.Value);
            }
        }
        return res;
    }

}

以上给出1种算法实现,以下是这个案例的输出结果:

5

分析:

显而易见,以上算法的时间复杂度为: O(n)

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/3800

发表评论

登录后才能评论