1

我在一次采访中被问到这个问题。第一部分相当简单，我必须编写代码来获取数组中连续整数的最大数量。以下是我写的代码：

int count = 0, max = 0;
for(int i = 1; i < array.length; i++) {
    if((array[i - 1] + 1) == array[i])) //curr is consecutive to prev
          count++;
    else
          count = 0; //reset the counter as sequence is broken

    //Keep track of maximum
    if(count > max)
         max = count;
}

System.out.println(max); //print the length of largest consecutive integers

第二部分是关于它的后续问题：

您将如何修改此逻辑以适用于存储在多台机器中的数组？

4

2 回答 2

0

假设我们将整个数组从左到右依次分配给每台机器。例如，只有两台机器（machine1和machine2），我们将数组分配0.... i到machine1和i + 1....n到machine2。从每台机器上，我们可以返回几个附加信息以及局部最大值。

class result {
    public int machineId;
    public int maxSoFar; // the max value as your code
    public int leftElement; // the leftmost element
    public int leftLength; // number of times the leftElement appears consecutively in left
    public int rightElement; // the rightmost element
    public int rightLength;  // number of times the rightElement appears consecutively in right
};

在合并两台机器的结果期间，对于任何machineId连续的两台机器（例如 3 和 4），我们可以像这样最大化 -

return Math.max(((machine1.rightElement == machine2.leftElement) ? machine1.rightLength + machine2.leftLength : 0), 
                  Math.max(machine1.maxSoFar, machine2.maxSoFar));
于 2017-03-24T09:46:21.113 回答
0

您可以使用Reduce Parallel Pattern来实现它

Python 中的示例（抱歉命名错误）：

def longest_seq(seq):

    Result = namedtuple("Result", ["left", "left_n", "max_n", "right", "right_n", "is_const"])

    def _longest_seq(seq):
        if 1 == len(seq):
            x = seq[0]
            return Result(left=x, left_n=1, max_n=1, is_const=True, right=x, right_n=1)

        l_res = _longest_seq(seq[0: int(len(seq) / 2)])
        r_res = _longest_seq(seq[int(len(seq) / 2): len(seq)])

        left_n = l_res.left_n + r_res.left_n if l_res.is_const and l_res.right == r_res.left else l_res.left_n
        right_n = r_res.right_n + l_res.right_n if r_res.is_const and r_res.left == l_res.right else r_res.right_n
        max_n = max(l_res.max_n, r_res.max_n, l_res.right_n + r_res.left_n if l_res.right == r_res.left else 0)
        is_const = l_res.is_const and r_res.is_const and l_res.right == r_res.left

        return Result(left=l_res.left,
                      left_n=left_n,
                      max_n=max_n,
                      right=r_res.right,
                      right_n=right_n,
                      is_const=is_const)

    return _longest_seq(seq).max_n
于 2017-03-08T02:52:02.850 回答