Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

preface

The longest continuous sequence of question 128 is as follows:

Given an unsorted integer array nums, find the length of the longest sequence in which numbers are consecutive (no sequence elements are required to be consecutive in the original array).

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

Example 1:

Input: nums = [100,4,200,1,3,2] output: 4 explanation: the longest sequence of consecutive digits is [1, 2, 3, 4]. It has length 4.Copy the code

A, thinking

The topic is relatively simple and easy to understand. A simpler way to think about it is to iterate twice: iterate through the array, ordering it from smallest to largest. Then walk through the array again to find the maximum continuous length.

I started with a two-pass approach, submitting the code and finding that I couldn’t pass all the test cases. When sorting an array, duplicate elements need to be removed. Otherwise, the calculation of the longest continuous length will be inaccurate.

I notice later that I’m going to use an O(N) algorithm, so how do I make it O(N)?

We realized that the hash table can effectively avoid the time complexity of traversing arrays, so we can use hashSets to store elements in arrays. (Of course, you can also use HashMap, key store value, value store null).

The general idea of implementation is as follows:

  1. Iterate over the array, storing the elements of the array into a hash table
  2. To avoid traversing the entire array, we can select only elements larger than the current one1Elements for statistics. That is, if the previous digit of the current value is in the hash table, it can be skipped
  3. Returns the maximum continuous length

For example

Nums = [100,4,200,1,3,2] is used as an example

  1. Put the array into the hash table
  2. If I walk through the hash table, the first element I get is1. At this time0It’s not in the hash table, so it goes back until4, the update result is4.
  3. The hash table takes the second element2At this time,1In the hash table, so skip. Syntactic skipping3 和 4
  4. As for the100 和 200The longest length of is1
  5. Returns the result4

Second, the implementation

The implementation code

The implementation code is consistent with the idea

public int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int num : nums) {
        set.add(num);
    }
    int ret = 0;

    for (int num : set) {
        if(! set.contains(num -1)) {
            int currentNum = num;
            int currentRet = 1;

            while (set.contains(currentNum + 1)) {
                currentNum += 1;
                currentRet += 1; } ret = Math.max(ret, currentRet); }}return ret;
}
Copy the code

The test code

Public static void main(String[] args) {int[] nums = {100, 200,1,3,2}; Int [] nums1 = {,0,5,8,1,4,7,3, 9-1, 1, 6}; Int [] nums2 =,2,0,1 {1}; new Number128().longestConsecutive(nums); }Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥

If you think my writing is good, you might as well give me a thumbs-up! If you have any questions, please see the comments section