다음과 같은 I 배열이 주어 배열

Question

연속적인 정수 소자의 수를 계산 :

arr = [8, 13, 14, 10, 6, 7, 8, 14, 5, 3, 5, 2, 6, 7, 4] 

I는 연속 번호 시퀀스의 수를 카운트하고 싶다. 예를 들어 위의 배열에서 연속 번호 시퀀스 (또는 배열 슬라이스)는 다음과 같습니다.

[13,14] 
[6,7,8] 
[6,7] 

따라서 3 개의 슬라이스가 있습니다. 이것을 계산하는 효율적인 알고리즘이란 무엇입니까? 나는 내가 그것을 할 수있는 방법을 알고있다. (N^2)하지만 나는 그것보다 나은 것을 찾고있다.

Answer 1

arr = [8, 13, 14, 10, 6, 7, 8, 14, 5, 3, 5, 2, 6, 7, 4] 
result = [] 
stage = [] 
for i in arr: 
    if len(stage) > 0 and i != stage[-1]+1: 
     if len(stage) > 1: 
      result.append(stage) 
     stage = [] 
    stage.append(i) 
print result 

---

출력 :

[[13, 14], [6, 7, 8], [6, 7]] 

코드의 시간 복잡도 O (N)이다. (이 하나의 for 루프입니다 그리고 그것은 루프의 각 반복이 O (1) 것을 볼 어렵지 않다..)

Answer 2

이것은 O (N) 시간에 수행 할 수 있다고 생각합니다. 개수를 원할 경우

1. 배열을 반복합니다. 카운터를 0으로 초기화하십시오.
2. 다음 요소가 현재 요소보다 하나 또는 하나 작 으면 카운터를 증가시킵니다.
3. 다음 요소가 현재 요소보다 하나 이상 작지 않을 때까지 계속 반복합니다.
4. 끝까지 도달 할 때까지 2 단계와 3 단계를 반복하십시오.

당신은 배열을 통해 지속적으로 증가하는 연속적인 요소의 섹션 (귀하의 질문에서 명확하지)

1. 반복 처리를합니다. 카운터를 0으로 초기화하십시오.
2. 다음 요소가 현재 요소보다 하나 많으면 카운터를 증가시킵니다.
3. 다음 요소가 현재 요소 중 하나가 아닐 때까지 계속 반복합니다.
4. 끝까지 도달 할 때까지 2 단계와 3 단계를 반복하십시오.

Answer 3

arr = [8, 13, 14, 10, 6, 7, 8, 14, 5, 3, 5, 2, 6, 7, 4] 
p arr.each_cons(2).chunk{|a,b| a.succ == b || nil}.count #=> 3 

nil는 chunk -method에 특별한 의미가 있습니다 : 그것은 항목이 삭제되도록합니다.

Answer 4

내가 Enumerable#slice_before을 사용하여 다음과 같이 할 것 :

는

a = [8, 13, 14, 10, 6, 7, 8, 14, 5, 3, 5, 2, 6, 7, 4] 
prev = a[0] 
hash = Hash[a.slice_before do |e| 
    prev, prev2 = e, prev 
    prev2 + 1 != e 
end.map{|e| [e,e.size] if e.size > 1}] 
hash # => {[13, 14]=>2, [6, 7, 8]=>3, [6, 7]=>2} 
hash.size # => 3