首页 / 算法 / 一题算法|求最长和谐子序列
一题算法|求最长和谐子序列
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了一题算法|求最长和谐子序列,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2753字,纯文字阅读大概需要4分钟。
内容图文
和谐子序列的定义
和谐数组是指一个数组里元素的最大值和最小值之间的差别正好是1,也就是说我们需要找出比该元素大于或者相等的元素
LeetCode 题目:
给定一个整数数组,你需要在所有可能的子序列中找到最长的和谐子序列的长度
题目示例:
输入: [1,3,2,2,5,2,3,7]
输出: 5
原因: 最长的和谐数组是:[3,2,2,2,3].
解法一:暴力枚举法
暴力枚举的思想很简单,也是我们常用的方法,就是双重遍历数组,第一层遍历是枚举数组中的每一个元素并且假设该元素是数组中最小的元素,第二层遍历是枚举元素与该数组中的每一个元素逐一比较,找出等于枚举元素或者比枚举元素大一的元素,统计出最终的元素个数。
1、解题代码
/**
* 使用暴力枚举的方式
* 双重循环,每次以当前遍历的元素当作最小元素,然后统计该数组中比该元素大1的个数或者相等的元素,最后返回最大的那个数
*
* @param nums 传入的数组
* @return
*/
public static int findLHS(int[] nums) {
// 记录最大的和谐子序列长度
int res = 0;
// 第一层遍历,当前元素默认为最小的元素
for (int i = 0; i < nums.length; i++) {
// 当前元素最长的子序列长度
int count = 0;
// 第二层遍历,与数组中的每一个元素进行比较,找出 nums[i]+1 = nums[j] 或者 nums[i]==nums[j] 的元素个数
for (int j = 0; j < nums.length; j++) {
if (nums[i] + 1 == nums[j] || nums[i] == nums[j]) {
count += 1;
}
}
// 将最大的赋值给res
res = Math.max(count, res);
}
return res;
}
2、复杂度分析
时间复杂度:因为是双层循环遍历,所以时间复杂度是O(N^2)
空间复杂度:在双层遍历中,并没有产生额外的数组,只是定义了两个临时遍历,所以空间复杂度为O(1)
解法二:两次遍历 + HashMap
HashMap + 两次遍历的思想也比较简单,第一次遍历是统计每个元素出现的次数,并且将元素的值作为key,出现的次数作为val 存入到 HashMap 中,第二次遍历是遍历 HashMap ,判断 HashMap 中是否存在比当前key+1的key,如果存在这统计出这两个key一共出现的次数,最后返回出现最多的次数。
1、解题代码
/**
* hashMap + 两次循环
* 第一次循环是统计每个元素出现的个数
* 第二次循环是遍历HashMap 集合,判断map集合中是否存在比当前key大于1的key,如果存在就统计两个key一共出现的次数
*
* @param nums
* @return
*/
public static int findLHSByHashMap(int[] nums) {
// 记录最大的和谐子序列长度
int res = 0;
Map<Integer, Integer> hashMap = new HashMap<>();
// 第一层遍历,当前元素默认为最小的元素
for (int i = 0; i < nums.length; i++) {
hashMap.put(nums[i], hashMap.getOrDefault(nums[i], 0) + 1);
}
// 遍历整个map
for (int key : hashMap.keySet()) {
if (hashMap.containsKey(key + 1)) {
res = Math.max(res, hashMap.get(key) + hashMap.get(key + 1));
}
}
return res;
}
2、复杂度分析
时间复杂度:虽然遍历了两次,但是没有出现双层循环,所以时间复杂度是O(N)
空间复杂度:这里新增了 HashMap 的对象,所以空间复杂度为O(N)
解法三:单次遍历 + HashMap
这种方法是前面一种方法的优化,将两次循环优化成一次循环,可以提升代码的执行效率,思想也比较简单,就是将元素 X 添加到 Map 集合后,同时判断出 X 与 X-1 组成的和谐数组长度和 X 与 X+1 组成的和谐数组长度,取两者中最大的一个。
1、解题代码
/**
* hashmap+单次遍历
* 是一种方法中的改进,在将元素添加到 map 的时候
* 就计算出计算出元素 X 与 X-1 的和谐数组的长度和 X 与 X+1 的和谐数组长度
* 这种方式虽然时间复杂度跟上一种没什么区别,但是可以节约执行时间
* @param nums
* @return
*/
public static int findLHSByMap(int[] nums) {
// 记录最大的和谐子序列长度
int res = 0;
Map<Integer, Integer> hashMap = new HashMap<>();
// 第一层遍历,当前元素默认为最小的元素
for (int i = 0; i < nums.length; i++) {
hashMap.put(nums[i], hashMap.getOrDefault(nums[i], 0) + 1);
// 判断是否包含key+1的key
if (hashMap.containsKey(nums[i] + 1)) {
res = Math.max(res, hashMap.get(nums[i]) + hashMap.get(nums[i] + 1));
}
// 判断是否包含key-1的key
if (hashMap.containsKey(nums[i] - 1)) {
res = Math.max(res, hashMap.get(nums[i]) + hashMap.get(nums[i] - 1));
}
}
return res;
}
2、复杂度分析
时间复杂度:跟上面一样,时间复杂度是O(N)
空间复杂度:跟上面一样,空间复杂度为O(N)
最后
欢迎扫码关注微信公众号:「平头哥的技术博文」,和平头哥一起学习,一起进步。
原文:https://www.cnblogs.com/jamaler/p/12091363.html
内容总结
以上是互联网集市为您收集整理的一题算法|求最长和谐子序列全部内容,希望文章能够帮你解决一题算法|求最长和谐子序列所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。