Simple Java Sort Solution (beat 97.9%)


  • 4
    I
    public int findLHS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        Arrays.sort(nums);
        int start = 0;
        int nextstart = 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] - nums[start] == 1) {
                if (nums[nextstart] < nums[i]) {
                    nextstart = i;
                }
                res = Math.max(res, i - start + 1);
            } else if (nums[i] - nums[start] > 1) {
                start = start == nextstart ? i : nextstart;
                i--;
            }
        }
        return res;
    }
    

    Thanks all for the comments. I revised the code to make it easier to read and adjusted the percentage.


  • 0

    I dont think this is a O(n logn) solution, to get the for loop in O(n), everytime a need to move the start is detected, it needs to be from i.


  • 0
    I

    @johnyrufus16 Thanks for your comment. I optimized the code. Now it runs in 44 ms and beats 100%. Actually if we need to move start idx, we can't make it point to i directly. We need to use a variable to keep track of the next idx. Example would be 1, 1, 1, 2, 2, 3, 3, in this case, if i points to 3 where the idx is 5, we should change start idx to point to first 2's idx which is 3.


  • 1

    @ihaveayaya
    nice, you have optimized a lot, but we can still proceed in a fashion where stardIdx never needs to go back, here is my code (my code ooks a bit more stressful :) so not sure if its worth the effort):

    public static int findLHS(int[] nums) {
            if(nums.length < 2 ) return 0;
            Arrays.sort(nums);
            int count = 0;
    
            int res = Integer.MIN_VALUE;
    
            int curi = 0;
            int curj = 0;
    
            while(curj + 1 < nums.length && nums[curj + 1] == nums[0]) ++curj;
    
            for(int  nexti = curj+1; nexti < nums.length; nexti++) {
                int nextj = nexti;
                while(nextj + 1 < nums.length && nums[nextj + 1] == nums[nexti]) ++nextj;
                if(nums[curi] + 1 == nums[nexti]) {
                    res = Math.max(res, nextj - curi + 1);
                }
                curi = nexti;
                curj = nextj;
                nexti = curj;
            }
            return Math.max(res, count);
        }
    

  • 0
    I

    @johnyrufus16 Thanks for your post. I have already changed the way to traverse the array. Start idx now always increase.


  • 1
    D

    Why sorting O(nlogn) can beat normal HashMap O(n) solution ?


  • 1
    I

    @daniexia I think it's test case specific. Hashmap can introduce some overhead which would slow down the execution. We are not comparing runtime complexity here.


  • 1
    Y
    public class Solution {
        public int findLHS(int[] nums) {
            Arrays.sort(nums);
    
            int result = 0;
            int left = 0, right = 0;
    
            while (right < nums.length) {
                if (nums[right] - nums[left] < 1)
                    right++;
                else if (nums[right] - nums[left] == 1) {
                    result = Math.max(result, right - left + 1);
                    right++;
                } else
                    left++;
            }
    
            return result;
        }
    }
    

  • 0

    I think they changed the test cases further more only a month or so later. Now this algorithm is 55ms beats 92.23% according to my last submission(2017-07-02 00:38:02).


  • 0
    H
    This post is deleted!

  • 0
    H

    my code beats >94%

    public class Solution {
        public int findLHS(int[] nums) {
            if(nums == null || nums.length <= 1){
                return 0;
            }
            Arrays.sort(nums);
            int len = nums.length;
            int max = 0;
            int curr = 0;
            int small = 1;
            int large = 0;
            //分情况讨论:1.如果当前元素等于前一个元素(再继续判断它是属于小的还是大的)
            //2.如果当前元素值比前一个元素值大1(判断该元素是下一次比较的较大者,还是本次比较的较大者)
            //3.如果不符合上面两种情况,则重置large和small
            //每一轮比较,如果large不为0的话,说明有存在值相差1的序列对,则更新max的值
            for(int i = 1; i < len; i++){
                if(nums[i] == nums[i-1] + 1){
                    if(small == 0){
                        small = 1;
                    }else if(large != 0){
                        max = Math.max(max, large+small);
                        small = large;
                    }
                    large = 1;
                }else if(nums[i] == nums[i-1]){
                    if(large == 0){
                        small++;
                    }else{
                        large++;
                    }
                }else{
                    small = 1;
                    large = 0;
                }
                if(large != 0){
                    max = Math.max(max, large+small);
                } 
            }
            return max;
        }
    }
    

  • 1

    My clean version:

    public int findLHS(int[] nums) {
        int result = 0;   
        Arrays.sort(nums);
        int left = 0 , right = 1;
        //right is the subsequence's right RHS index and left is the subsequence's LHS index
        //namely: nums[right] is max, nums[left] is min
        while(right<nums.length){
            while(nums[right]-nums[left]>1) left++;  //in case of difference between max and min > 1             
            if(right-left+1>result&&nums[right]-nums[left]==1) result = right-left+1; //update result if new length: right-left+1> result and difference between max and min = 1 
            right++;
        }
        return result;
    }

  • 0

    @tongzhou2
    great solution!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.