分享一个大牛的人工智能教程。零基础通俗易懂风趣幽默希望你也加入到人工智能的队伍中来请轻击人工智能教程大家好欢迎来到我的网站 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑人工智能时代就要来临了科… 继续阅读 前言https://www.captainai.net/troubleshooterpackage live.every.day.ProgrammingDesign.CodingInterviewGuide.RecursionAndDynamicPrograming; import java.util.HashMap; /** * 数组中的最长连续序列 * * 【题目】 * 给定无序数组arr返回其中最长的连续序列的长度。 * * 【难度】 * 中等 * * 【解答】 * 本题利用哈希表可以实现时间复杂度为0(N)、额外空间复杂度为O(N)的方法。具体过程如下 * .生成哈希表HashMapInteger,Integermapkey代表遍历过的某个数value代表key这个数所在的最长连续序列的长度。 * 同时map还可以表示arr中的一个数之前是否出现过。 * .从左到右遍历arr假设遍历到arr[i]。如果arr[i]之前出现过直接遍历下一个数只处理之前没出现过的arr[i]。首先在 * map中加入记录(arr[i],1)代表目前arr[i]单独作为一个连续序列。然后看map中是否含有arr[i]-1如果有则说明 * arr[i]-1所在的连续序列可以和arr[i]合并合并后记为A序列。利用map可以得到A序列的长度记为lenA最小值记为leftA * 最大值记为rightA只在map中更新与leftA和rightA有关的记录更新成(leftA,lenA)和(rightA,lenA)。接下来看map中是 * 否含有arr[i]1如果有则说明arr[i]1所在的连续序列可以和A合并合并后记为B序列。利用map可以得到B序列的长度为 * lenB最小值记为leftB最大值记为rightB只在map中更新与leftB和rightB有关的记录更新成(leftB,lenB)和 * (rightB,lenB)。 * .遍历的过程中用全局变量max记录每次合并出的序列的长度最大值最后返回max。 * * 整个过程中只是每个连续序列最小值和最大值在map中的记录有意义中间数的记录不再更新因为再也不会使用到。这是因为我们 * 只处理之前没出现的数如果一个没出现的数能够把某个连续区间扩大或把某两个连续区间连在一起毫无疑问只需要map中有关 * 这个连续区间最小值和最大值的记录。 * * 具体过程请参看如下代码中的longestConsecutive方法。 * * author Created by LiveEveryDay */ public class ArrayLongestConsecutiveSequence { public static int longestConsecutive(int[] arr) { if (arr null || arr.length 0) { return 0; } int max 1; HashMapInteger, Integer map new HashMap(); for (int i 0; i arr.length; i) { if (!map.containsKey(arr[i])) { map.put(arr[i], 1); if (map.containsKey(arr[i] - 1)) { max Math.max(max, merge(map, arr[i] - 1, arr[i])); } if (map.containsKey(arr[i] 1)) { max Math.max(max, merge(map, arr[i], arr[i] 1)); } } } return max; } private static int merge(HashMapInteger, Integer map, int less, int more) { int left less - map.get(less) 1; int right more map.get(more) - 1; int len right - left 1; map.put(left, len); map.put(right, len); return len; } public static void main(String[] args) { int[] arr {100, 4, 200, 1, 3, 2}; System.out.printf(The length of longest consecutive sequence is: %d, longestConsecutive(arr)); } } // ------ Output ------ /* The length of longest consecutive sequence is: 4 */