给定一个无序的整数类型数组,求最长的连续元素序列的长度。
例如:
给出的数组为[1000, 4, 2000, 1, 3, 2],
最长的连续元素序列为[1, 2, 3, 4]. 返回这个序列的长度:4
你需要给出时间复杂度在O(n)之内的算法
public int longestConsecutive (int[] num) { // write code here int count = 1; if(num.length == 0){ return 0; } Set<Integer> set = new HashSet<>(); for(int n : num){ set.add(n); } for(int i = 0 ; i < num.length; i++){ int temp = num[i]; if(!set.contains(num[i])){ continue; } int l = temp - 1; int r = temp + 1; while(set.contains(l)){ set.remove(l--); } while(set.contains(r)){ set.remove(r++); } count = Math.max(count, r - l - 1); } return count; }
import java.util.*; public class Solution { /** * * @param num int整型一维数组 * @return int整型 */ public int longestConsecutive (int[] num) { Set<Integer> temp = new HashSet(); for(int n:num)temp.add(n); int max = 1; for(int n:num){ int count = 1; if(temp.remove(n)){ int up = n+1; int low = n-1; while(temp.remove(up++)){ count++; } while(temp.remove(low--)){ count++; } } max = Math.max(max,count); } return max; } }
提供另一种想法吧,已AC。 先初始化一个足够大的byte数组,为什么不用int数组是为了省点空间。 遍历num数组,同时将byte数组里面相应位置设为1,如遍历到56,就byte[56]=1, 遍历完后byte数组就会有0 1值,遍历byte数组,求得连续为1的长度最大的即可 public static int longestConsecutive (int[] num) { // write code here //记录数组里面的最大值和最小值 int max = 2,min = Integer.MAX_VALUE; for (int i : num) { if (i >max){ max = i; } if (i < min){ min = i; } } //max用于初始化byte数组的长度,为了防止数组里面的最大值小于数组本身的长度 max = max > num.length?max:num.length; byte[] bytes = null; if (min < 0){ //如{1,0,-1},min=-1,max=3,初始化输出长度为4个,多了也不碍事 //有负数时byte数组的前一部分用来表示负数是否存在,后一部分用来表示正数是否存在 bytes = new byte[max+1+Math.abs(min)]; for (int i : num) { //将相应位置置为1 bytes[i+Math.abs(min)] = 1; } }else { //num数组中全部为正数的情况,就不用为负数的判断留下额外空间了 bytes = new byte[max+1]; for (int i : num) { //将相应位置置为1 bytes[i] = 1; } } //maxCount记录最大程度 int maxCount = 1,tmpCnt=0; //遍历byte数组,byte数组里面就全是0 1值了 for (int i = 0; i < bytes.length; i++) { if (bytes[i] == 1){ tmpCnt++; }else { maxCount = tmpCnt > maxCount? tmpCnt : maxCount; tmpCnt = 0; } } return maxCount; }
import java.util.*; public class Solution { /** * * @param num int整型一维数组 * @return int整型 */ public int longestConsecutive (int[] num) { // write code here if(num.length==0) return 0; int ans=1; PriorityQueue<Integer>stack=new PriorityQueue<>(); for(int i=0;i<num.length;i++){ stack.add(num[i]); } int curLen=1; int preValue=stack.poll(); while(!stack.isEmpty()){ int curValue=stack.poll(); if(curValue-preValue==1){ curLen++; }else if(curValue-preValue==0){ continue; }else{ ans=Math.max(ans,curLen); curLen=1; } preValue=curValue; } ans=Math.max(ans,curLen); return ans; } }
import java.util.*; public class Solution { /** * 本来先排序再遍历一遍即可,时间复杂度O(nlogn) * 但是题目要求O(n),就只能时间换空间,通过哈希表 * 记录数组元素,然后遍历数组,去哈希表中找这个元 * 素所处的连续序列,得到序列长度,这里注意已经找 * 到的元素从哈希表中去除,不需要再次查找了,所有 * 元素只会被遍历两次,时间复杂度O(n) */ public int longestConsecutive(int[] nums) { Set<Integer> set = new HashSet<>(nums.length); for(int num:nums){ set.add(num); } int max = 0; for(int num:nums){ while(set.remove(num)){ int left = num, right = num; while(set.remove(left-1)) left--; while(set.remove(right+1)) right++; max = Math.max(max, right-left+1); } } return max; } }
import java.util.HashSet;
public class Solution {
public int longestConsecutive(int[] num) {
HashSet hset = new HashSet();
for (int n : num) {
hset.add(n);
}
int res = 0;
for (int n : num) {
if (hset.contains(n)) {
hset.remove(n);
int prev = n - 1;
int post = n + 1;
while (hset.contains(prev)) {
hset.remove(prev--);
}
while (hset.contains(post)) {
hset.remove(post++);
}
res = Math.max(res, post - prev - 1);
}
}
return res;
}
}
import java.util.*; public class Solution { public int longestConsecutive(int[] nums) { Arrays.sort(nums); int len = nums.length; int max =1; if(nums==null ||len==0) return -1; //int i=0; for(int i=0;i<len;i++){ int n = 1; for( int j =i+1;j<len;j++){ if(nums[j]-nums[i]==n){ n++; } } max =Math.max(n,max); } return max; } }
//我的思路比较简单,这里顺着思路可以很容易理解代码的意思。
代码如下:
public class Solution {
public int longestConsecutive(int[] num) {
if (num == null || num.length <= 0)
return 0;
if (num.length == 1)
return 1;
Arrays.sort(num);
int conseccutiveMaxCount = 1;
int conseccutiveCount = 1;
for (int i = 1; i < num.length; i++) {
if (num[i] - num[i - 1] == 0) {
continue;
} else if (num[i] - num[i - 1] == 1) {
conseccutiveCount++;
if (conseccutiveCount > conseccutiveMaxCount) {
conseccutiveMaxCount = conseccutiveCount;
}
continue;
}
conseccutiveCount = 1;
}
return conseccutiveMaxCount;
}
}
import java.util.HashSet;
import java.util.Set;
/**
* 复杂度分析o(n):HashSet查找的复杂度为o(1)
*/
public class Solution {
public int longestConsecutive(int[] num) {
Set dstcNum = new HashSet();
// 首先将数字去重
for (Integer i : num) {
dstcNum.add(i);
}
int res = 0;
for (Integer i : num) {
// 如果set中不包含该数字,也就是数字已经从set中删除了,那么我们选取下一个数字
if (!dstcNum.contains(i)) continue;
dstcNum.remove(i);
int prev = i - 1, post = i + 1;
while (dstcNum.contains(prev)) {
dstcNum.remove(prev--);
}
while (dstcNum.contains(post)) {
dstcNum.remove(post++);
}
res = Math.max(res, post - prev - 1);
}
return res;
}
}
import java.util.Arrays;
public class Solution {
public int longestConsecutive(int[] num) {
if (num == null || num.length == 0)
return 0;
quickSort(num, 0, num.length-1);
int curSeq = 0;
int maxSeq = 1;
for (int i = 0; i < num.length-1; i++) {
if (curSeq == 0)
curSeq++;
if (num[i] + 1 == num[i + 1]) {
curSeq++;
maxSeq = Math.max(curSeq, maxSeq);
} else if (num[i] == num[i+1]) {
} else {
curSeq = 0;
}
}
return maxSeq;
}
private void quickSort(int[] num, int low, int high) {
if (low < high) {
int pivot = partition(num, low, high);
quickSort(num, low, pivot -1);
quickSort(num, pivot+1, high);
}
}
private int partition(int[] num, int low, int high) {
int pivot = num[low];
while (low < high) {
while (low < high && num[high] >= pivot)
high--;
num[low] = num[high];
while (low<high && num[low] <= pivot)
low++;
num[high] = num[low];
}
num[low] = pivot;
return low;
}
}
import java.util.HashMap; public class Solution { //利用map的查找时间为o(1)的特性,拿空间换时间 public int longestConsecutive(int[] num) { if(num==null||num.length==0){ return 0; } if(num.length==1){ return 1; } HashMap<Integer,Boolean>map=new HashMap<>(); for(int i=0;i<num.length;++i){//将数组里的数存储进map map.put(num[i],true); } int pre;//当前数的前一个数 int curr;//当前数 int post;//后一个数 int max=1;//暂时的最大连续值 int maxmax=max;//我们记录的当前最大的连续值 for(int i=0;i<num.length;++i){ if(map.get(num[i])==true){//还未被访问 curr=num[i]; pre=num[i]-1; post=num[i]+1; while(map.containsKey(pre)){//一直找前面那个数 map.put(pre,false);//置值为false,下次不用再访问 max++;//最大连续数加一 pre--;//前面的那个数的数值减一 } while(map.containsKey(post)){//同上 map.put(post,false); max++; post++; } if(max>maxmax){//两个循环结束后,判断当前的最大连续值是否大于咱们存储的那个最大连续值 maxmax=max; } max=1;//置max为1 } } return maxmax; } }
import java.util.HashSet; public class Solution { public int longestConsecutive(int[] num) { if (num == null || num.length == 0) return 0; HashSet<Integer> set = new HashSet<Integer>(); for (int i = 0; i < num.length; ++i) { set.add(num[i]); } int longestNum = 0; while (!set.isEmpty()) { int temp = set.iterator().next(); int tempLongestNum = 1; set.remove(temp); int temp2 = temp; while(set.contains(++temp2)) { ++tempLongestNum; set.remove(temp2); } temp2 = temp; while(set.contains(--temp2)) { ++tempLongestNum; set.remove(temp2); } if (tempLongestNum > longestNum) longestNum = tempLongestNum; } return longestNum; } }
import java.util.*; public class Solution { /** * 1.先把数字放到一个集合中,拿到一个数字,就往其两边搜索,得到包含这个数字的最长串, * 2.并且把用过的数字从集合中移除(因为连续的关系,一个数字不会出现在两个串中)。 * 3.最后比较当前串是不是比当前最大串要长,是则更新。如此继续直到集合为空。 * @param num * @return */ public int longestConsecutive(int[] num) { if(num==null||num.length==0) return 0; int res=1; Set<Integer> numbers=new HashSet<>(); for(int val:num){ numbers.add(val); } while(!numbers.isEmpty()){ int len=1; Iterator iterator=numbers.iterator(); int cur=(int)iterator.next(); numbers.remove(cur); int left=cur-1,right=cur+1; while (numbers.contains(left)){ len++; numbers.remove(left--); } while(numbers.contains(right)){ len++; numbers.contains(right++); } res=len>res?len:res; } return res; } }
public int longestConsecutive(int[] num) { int res = 0; HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int n : num) { if (!map.containsKey(n)) { int left = (map.containsKey(n - 1)) ? map.get(n - 1) : 0; int right = (map.containsKey(n + 1)) ? map.get(n + 1) : 0; // sum: length of the sequence n is in int sum = left + right + 1; map.put(n, sum); // keep track of the max length res = Math.max(res, sum); // extend the length to the boundary(s) // of the sequence // will do nothing if n has no neighbors map.put(n - left, sum); map.put(n + right, sum); } else { // duplicates continue; } } return res; }