LeetCode-128-最长连续序列(Leetcode-128-longest continuous sequence)

最长连续序列

题目描述:给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例说明请见LeetCode官网。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-consecutive-sequence/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

题目描述:给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例说明请见LeetCode官网。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-consecutive-sequence/
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解法一:哈希表

因为哈希查找比较快,所以用哈希表来辅助计算,具体处理过程如下:

首先,用HashSet将原数组中的数字去重得到numsSet;
然后,遍历numsSet中的所有数字,用currentConsecutiveNums记录以当前数字为起点,连续的数且在numsSet中的最长序列长度,通过哈希查找在numsSet中查找这些连续的数字,最后得到当前数字对应的最长连续序列长度;
如果当前数字对应的最长连续序列长度比已知的最长连续序列longestConsecutiveNums大,则更新最长连续序列longestConsecutiveNums的值。

最后,返回longestConsecutiveNums即为连续的最长序列的长度。

因为哈希查找比较快,所以用哈希表来辅助计算,具体处理过程如下:

  • 首先,用HashSet将原数组中的数字去重得到numsSet;
  • 然后,遍历numsSet中的所有数字,用currentConsecutiveNums记录以当前数字为起点,连续的数且在numsSet中的最长序列长度,通过哈希查找在numsSet中查找这些连续的数字,最后得到当前数字对应的最长连续序列长度;
  • 如果当前数字对应的最长连续序列长度比已知的最长连续序列longestConsecutiveNums大,则更新最长连续序列longestConsecutiveNums的值。

最后,返回longestConsecutiveNums即为连续的最长序列的长度。

import java.util.HashSet;
import java.util.Set;

public class LeetCode_128 {
    /**
     * 哈希表
     *
     * @param nums
     * @return
     */
    public static int longestConsecutive(int[] nums) {
        // 去重后的数
        Set<Integer> numsSet = new HashSet<>();
        for (int num : nums) {
            numsSet.add(num);
        }

        // 记录最长的连续序列
        int longestConsecutiveNums = 0;

        for (Integer num : numsSet) {
            if (!numsSet.contains(num - 1)) {
                // 当前的数
                int currentNum = num;
                // 当前的数连续的序列的长度,初始值为1
                int currentConsecutiveNums = 1;

                // 获取以当前数字为起点,连续的数且在numsSet中的长度
                while (numsSet.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentConsecutiveNums += 1;
                }

                // 如果当前的最大连续长度大于最大的的连续序列,则更新最大的连续序列
                longestConsecutiveNums = Math.max(longestConsecutiveNums, currentConsecutiveNums);
            }
        }
        return longestConsecutiveNums;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{100, 4, 200, 1, 3, 2};
        // 测试用例,期望输出: 4
        System.out.println(longestConsecutive(nums));
    }
}

【每日寄语】 第一个青春是上帝给的;第二个的青春是靠自己努力的。

【每日寄语】 第一个青春是上帝给的;第二个的青春是靠自己努力的。

————————

Longest continuous sequence

Title Description: given an unordered integer array nums, find the length of the longest sequence of numbers (sequence elements are not required to be continuous in the original array).
Please design and implement an algorithm with time complexity O (n) to solve this problem.
See leetcode’s official website for an example.
Source: leetcode
Link: https://leetcode-cn.com/problems/longest-consecutive-sequence/
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.

Title Description: given an unordered integer array nums, find the length of the longest sequence of numbers (sequence elements are not required to be continuous in the original array).

Please design and implement an algorithm with time complexity O (n) to solve this problem.

See leetcode’s official website for an example.

Source: leetcode
Link: https://leetcode-cn.com/problems/longest-consecutive-sequence/
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.

Solution 1: hash table

Because the hash lookup is fast, the hash table is used to assist the calculation. The specific processing process is as follows:
Firstly, use HashSet to duplicate the numbers in the original array to get numset;
Then, traverse all the numbers in numsset, record the continuous numbers starting from the current number and the longest sequence length in numsset with currentconsequentialnums, find these continuous numbers in numsset through hash search, and finally get the longest continuous sequence length corresponding to the current number;
If the length of the longest continuous sequence corresponding to the current number is greater than the known longest continuous sequence longestconsequentialnum, the value of the longest continuous sequence longestconsequentialnum is updated.
Finally, the length of the longest consecutive sequence is returned.

Because the hash lookup is fast, the hash table is used to assist the calculation. The specific processing process is as follows:

  • Firstly, use HashSet to duplicate the numbers in the original array to get numset;
  • Then, traverse all the numbers in numsset, record the continuous numbers starting from the current number and the longest sequence length in numsset with currentconsequentialnums, find these continuous numbers in numsset through hash search, and finally get the longest continuous sequence length corresponding to the current number;
  • 如果当前数字对应的最长连续序列长度比已知的最长连续序列longestConsecutiveNums大,则更新最长连续序列longestConsecutiveNums的值。

Finally, the length of the longest consecutive sequence is returned.

import java.util.HashSet;
import java.util.Set;

public class LeetCode_128 {
    /**
     * 哈希表
     *
     * @param nums
     * @return
     */
    public static int longestConsecutive(int[] nums) {
        // 去重后的数
        Set<Integer> numsSet = new HashSet<>();
        for (int num : nums) {
            numsSet.add(num);
        }

        // 记录最长的连续序列
        int longestConsecutiveNums = 0;

        for (Integer num : numsSet) {
            if (!numsSet.contains(num - 1)) {
                // 当前的数
                int currentNum = num;
                // 当前的数连续的序列的长度,初始值为1
                int currentConsecutiveNums = 1;

                // 获取以当前数字为起点,连续的数且在numsSet中的长度
                while (numsSet.contains(currentNum + 1)) {
                    currentNum += 1;
                    currentConsecutiveNums += 1;
                }

                // 如果当前的最大连续长度大于最大的的连续序列,则更新最大的连续序列
                longestConsecutiveNums = Math.max(longestConsecutiveNums, currentConsecutiveNums);
            }
        }
        return longestConsecutiveNums;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{100, 4, 200, 1, 3, 2};
        // 测试用例,期望输出: 4
        System.out.println(longestConsecutive(nums));
    }
}

[daily message] the first youth is given by God; The second youth depends on their own efforts.

[daily message] the first youth is given by God; The second youth depends on their own efforts.