실질적으로 큰 배열 (여러 시스템에 걸쳐 있음)에서 가장 큰 연속 정수를 얻는 방법

Question

인터뷰에서이 질문을했습니다. 첫 번째 부분은 배열에서 연속 된 정수의 최대 개수를 얻기위한 코드를 작성해야하는 매우 간단했습니다.

방법이 논리를 수정하는 것이 여러 시스템에 저장되어있는 배열 위해 일 :

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 

두 번째 부분은 그것을 질문을 따라했다 : 내가 쓴 코드는 다음?

Answer 1

당신은 (불량 인 이름을 죄송합니다) 파이썬에서 Reduce Parallel Pattern

예를 사용하여 구현할 수 있습니다

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 

Answer 2

한다고 가정 우리가 배포하는 전체 배열은 각 시스템에 순차적으로 왼쪽에서 오른쪽으로. 예를 들어, 두 대의 기계 (machine1 및 machine2)에 대해서만 0.... i을 machine1 및 i + 1....n을 machine2으로 분배합니다. 각 시스템에서 로컬 최대 값과 함께 몇 가지 추가 정보를 반환 할 수 있습니다. 그 machineId 연속이다 두 기계, 두 기계의 결과를 병합하는 동안

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 
}; 

(예를 들어, 3, 4). 우리는 다음과 같이 극대화 할 수 있습니다 -

return Math.max(((machine1.rightElement == machine2.leftElement) ? machine1.rightLength + machine2.leftLength : 0), 
        Math.max(machine1.maxSoFar, machine2.maxSoFar));