一、題目大意
https://leetcode.cn/problems/longest-harmonious-subsequence
和諧陣列是指一個陣列里元素的最大值和最小值之間的差別 正好是 1 ，
現在，給你一個整數陣列 nums ，請你在所有可能的子序列中找到最長的和諧子序列的長度，
陣列的子序列是一個由陣列派生出來的序列，它可以通過洗掉一些元素或不洗掉元素、且不改變其余元素的順序而得到，
示例 1：
輸入：nums = [1,3,2,2,5,2,3,7]
輸出：5
解釋：最長的和諧子序列是 [3,2,2,2,3]
示例 2：
輸入：nums = [1,2,3,4]
輸出：2
示例 3：
輸入：nums = [1,1,1,1]
輸出：0
提示：
- 1 <= nums.length <= 2 * 104
- -109 <= nums[i] <= 109
二、解題思路
思路：題目給我們一個陣列，讓我們找出最長的和諧子序列，和諧子序列就是序列中陣列的最大最小差值均為1，這里只讓我們求長度，而不需要回傳具體的子序列，所以我們可以對陣列進行排序，實際上只要找出來相差為1的兩個數的總共出現個數就是一個和諧子序列長度了，
三、解題方法
3.1 Java實作
public class Solution {
public int findLHS(int[] nums) {
Map<Integer, Integer> countMap = new HashMap<>();
for (int num : nums) {
countMap.put(num, countMap.getOrDefault(num, 0) + 1);
}
// a-b由小到大 b-a由大到小
PriorityQueue<Map.Entry<Integer, Integer>> priorityQueue
= new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getKey));
for (Map.Entry<Integer, Integer> entry : countMap.entrySet()) {
priorityQueue.add(entry);
}
int ans = 0;
Map.Entry<Integer, Integer> pre = priorityQueue.poll();
while (!priorityQueue.isEmpty()) {
Map.Entry<Integer, Integer> cur = priorityQueue.poll();
if (cur.getKey() - pre.getKey() == 1) {
ans = Math.max(ans, cur.getValue() + pre.getValue());
}
pre = cur;
}
return ans;
}
}
四、總結小記
- 2022/8/24 什么時候能水果自由呀
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/502641.html
標籤：其他