查网站域名备案,页面设计存在的问题,部门网站建设存在的问题,广州 环保 凡人网站建设文章目录题目描述思路 代码变式题#xff1a;返回答案数组更新可恶。。居然碰到了周一面试没撕出最优复杂度的题 题目描述
难点在于时间复杂度O(n)#xff0c;否则来个sort()还是很轻松的
思路 代码
一般来说#xff0c;时间复杂度可以用空间复杂度来弥补 代码变式题返回答案数组更新可恶。。居然碰到了周一面试没撕出最优复杂度的题 题目描述
难点在于时间复杂度O(n)否则来个sort()还是很轻松的
思路 代码
一般来说时间复杂度可以用空间复杂度来弥补来选个数据结构吧显而易见哈希表K - V 数组元素 - 以该元素为端点的序列的最长值状态转移方程now left right 1最优子结构left rightput(i ,now) 只是为了 containsKey() 判断状态转移还得看端点。
class Solution {public int longestConsecutive(int[] nums) { int ans 0;// 元素 - 连续值MapInteger, Integer hashmap new HashMap();for(int i : nums){// 新值存入情况if(!hashmap.containsKey(i)){// 左边、右边的所处端点值int left hashmap.get(i - 1) ! null ? hashmap.get(i - 1) : 0;int right hashmap.get(i 1) ! null ? hashmap.get(i 1) : 0;int now left right 1;ans Math.max(now, ans);// 只存端点即可具体原因可自己手写流程hashmap.put(i - left, now);hashmap.put(i right, now);// 1. 为 containsKey 服务 2. 可能当前点就是端点hashmap.put(i, now);}}return ans;}
}
// 变式返回答案数组维护一个index随着ans更新而更新 index i - left最后按照 index ans 创造新数组即可变式题返回答案数组
维护一个index随着ans更新而更新 index i - left最后按照 index ans 创造新数组即可
更新
经典空间换时间注意 temp 也要 put 进去因为 containsKey 要用
class Solution {public int longestConsecutive(int[] nums) {int ans 0;MapInteger, Integer hashmap new HashMap();for(int temp : nums) {if(!hashmap.containsKey(temp)) {int left hashmap.get(temp - 1) null ? 0 : hashmap.get(temp - 1);int right hashmap.get(temp 1) null ? 0 : hashmap.get(temp 1);int now left right 1;ans Math.max(now, ans);hashmap.put(temp - left, now);hashmap.put(temp right, now);hashmap.put(temp, now);}}return ans;}
}
