求解无序数组最长连续字串的长度

[编程题]求解无序数组最长连续字串的长度

热度指数：128 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

求解无序数组最长连续字串的长度，时间复杂度控制在O(n)

示例1

输入

[1,6,3,9,5,7,10,8,11,0,12]

输出

说明

该示例中，无序数组最长连续字串为[5,6,7,8,9,10,11,12]，长度是8

算法知识视频讲解

pein531

其实就是求上升子序列的最大长度

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 求解无序数组最长连续字串的长度
     * @param input_list int整型一维数组 输入的数组
     * @return int整型
     */
    public int search_max_continue_sub (int[] input_list) {
        // write code here
        HashSet<Integer> set = new HashSet<>();
        // 先将所有的数组元素存入set中，以便后续的查询达到复杂度O(1)
        for(int num: input_list) set.add(num);
        int maxLen = 1;
        // 遍历每个元素
        for(int i = 0; i < input_list.length; i++){
            int temp_maxLen = 1;
            int num = input_list[i];
            // 对当前元素不断减1，查看是否还在数组中，如果还在则更新最大长度
            while(set.contains(num - 1)){
                temp_maxLen ++;
                num --;
            }
            maxLen = Math.max(maxLen, temp_maxLen);
        }
        return maxLen;
    }
}

编辑于 2021-01-20 13:56:10 回复(2)

小黄圆圆

排序 + 线性 dp

import java.util.*;
 
 
public class Solution {
    public int search_max_continue_sub (int[] arr) {
        Arrays.sort(arr);
        int n = arr.length;
        int[] dp = new int[n]; // dp[i] 表示i前最长的连续上升数组的长度
        dp[0] = 1;
        int max = 1; // 记录最大值
        for (int i = 1; i < n; i++) {
            if (arr[i] - arr[i - 1] == 1) {
                dp[i] = dp[i - 1] + 1;
            } else {
                dp[i] = 1;
            }
            max = Math.max(dp[i], max); // 更新最大值
        }
        return max;
    }
}

发表于 2023-09-13 15:38:35 回复(0)

顶呱呱的无情编码机器

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 求解无序数组最长连续字串的长度
 * @param input_list int整型一维数组 输入的数组
 * @param input_listLen int input_list数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
void swap(int *p,int len)
{
    for(int i = 0;i<len-1;i++)
    {
        for(int j = 0;j<len-i-1;j++)
        {
            if(p[j]>p[j+1])
            {
                int temp =p[j];
                p[j]=p[j+1];
                p[j+1]=temp;
            }
        }
    }
}
int search_max_continue_sub(int* input_list, int input_listLen ) {
    swap(input_list,input_listLen);
    int *ptr=input_list;
    int MaxLen=0;
    do
    {
        int i =0;
        while(*(ptr+1)-(*ptr)==1)
        { 
          i++;
          ptr++;
        }
        MaxLen=((MaxLen)>(i)?(MaxLen):(i));
        ptr++;
    }while(*ptr);
      return MaxLen+1;  
        
}

发表于 2023-03-07 09:26:44 回复(0)