查找子数组的最大长度，其中每个元素覆盖一个完整的整数范围

Question

我有一个关于Hackkerrank的挑战如下

示例

票=[8,5,4,8,4]

已排序的有效子序列为{4,4,5}和{8,8}。这些子序列的m值分别为3和2。返回3。

功能描述

在下面的编辑器中完成maxTickets函数。

int tickets[n]:  an array of integers

int:  an integer that denotes the maximum possible value of m

1 ≤ n ≤ 10^5
1 ≤ tickets[i] ≤ 10^9

采样输入0

STDIN函数

4张票[]大小n=4

2

3

示例输出0

import java.util.*;

public class MaxTickets {

    public static void main(String[] args) {
        test(4,13,2,4,3);
        test(10,1,5,2,5,5,2,6,3,5,3);
        test(10,1,5,1,2,5,5,2,6,3,5,3);
        test(9,1,4,5,2,2,3,1,6,9,10);
        test(1,2,4,7,8,11,22);
        test(1,2,2,2,3,4,7,8,11,14,22);
        test(1,1,2,4,4,4,7,8,11,22);
    }

    static int maxTickets(List<Integer> tickets) {
        Collections.sort(tickets);
        tickets.forEach(num -> System.out.print(num + " "));

        List<Integer> list = new ArrayList<>();
        int len = tickets.size();
        int distance;
        int curDistance = Integer.MIN_VALUE;
        int lastDistance = Integer.MIN_VALUE;
        boolean first = true;

        for(int i = 1; i < len; i++) {
            int left = tickets.get(i-1);
            int right = tickets.get(i);
            distance = right - left;

            if(i == 1) {
                updateSum(list, 2);
            } else {
                if(lastDistance == 0 && first) {
                    updateSum(list, 1);
                }
                else if(distance == 0 ||
                    distance == curDistance) {
                    updateSum(list, 1);
                } else if(distance != curDistance) {
                    list.add(1);
                }
            }

            if(distance != 0) {
                curDistance = distance;
            }
            lastDistance = distance;
            if(i >= 2) {
                first = false;
            }
        }

        return
        list.stream()
            .max(Comparator.comparingInt(i  -> i))
            .get();

    }

    private static void updateSum(List<Integer> list, int value) {
        if(list.isEmpty()) {
            list.add(value);
        } else {
            int lastIndex = list.size() - 1;
            list.set(lastIndex, list.get(lastIndex) + value);
        }
    }

    private static void test(Integer... numbers) {
        List<Integer> list = Arrays.asList(numbers);
        int result = maxTickets(list);
        System.out.println("\n" + result);
    }

}

输出：

2 3 4 4 13 
4
1 2 2 3 3 5 5 5 5 6 10 
5
1 1 2 2 3 3 5 5 5 5 6 10 
6
1 1 2 2 3 4 5 6 9 9 10 
8
1 2 4 7 8 11 22 
2
1 2 2 2 3 4 7 8 11 14 22 
6
1 1 2 4 4 4 7 8 11 22 
3

我的代码能用吗？有没有我的代码失败的情况？你能为这个挑战提供一个更好的算法吗？

Answer 1

解决这个问题最简单（也是最快）的方法是使用最简单、最直接的算法。下面是一个描述它的伪代码。

Function unbroken_range(arr) {
    n = arr.length;
    sorted_arr = sort(arr);
    range_start = 0;
    best_len = 0;
    for i from 1 to n-1:
        if sorted_arr[i] - sorted_arr[i-1] > 1 then {
            current_len = i - range_start;
            if current_len > best_len then {
                best_len = current_len;
            }
            range_start = i;
        }
    }
    return max(n - range_start, best_len);
}   

从输出的外观来看，似乎是您的程序完成了这项工作。我没有详细讨论它，但您可以将它与伪代码进行比较，看看算法结构是否相似（应该如此，这确实是处理它的最简单的方法）。