計數連續的整數元素的數目在給定我有一個陣列，例如如下的陣列

：計數連續的整數元素的數目在給定我有一個陣列，例如如下的陣列

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

我想計數連續數序列的數目。例如在上面的數組中，連續數字序列（或數組片）是：

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

因此我們有3個這樣的片。什麼是有效的算法來計算這個？我知道我怎麼能做到O（N^2），但我在尋找比這更好的東西。

來源

2013-12-18 Jasdeep Singh

我不認爲[ 6,7,8]是一對。你在尋找所有連續的序列嗎？ –

對不起 - 是連續序列。編輯問題。 –

爲什麼不是[7,8]有效的一對？ – Skyler

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）。）

來源

2013-12-18 17:37:26 Skyler

我認爲你剛剛在Python中回答了Ruby的問題:) –

@JonClements無關緊要 - 我只需要了解如何在O（N）中完成這項工作，我可以自己將其轉換爲Ruby。這看起來不錯:) –

@JasdeepSingh只有一個'for'循環。並且不難看出循環中的每個迭代都是O（1）。 – Skyler

我認爲這可以在O（N）時間完成。如果你只是想計數，

遍歷數組。將計數器初始化爲0.
如果下一個元素多於或少於當前元素，則遞增計數器。
繼續迭代，直到下一個元素不多於或少於當前元素。
重複第2步和第3步，直到最後。

如果你想不斷增加連續元素的部分（而不是從你的問題清楚）

通過數組迭代。將計數器初始化爲0.
如果下一個元素比當前元素多一個，則遞增計數器。
繼續迭代直到下一個元素不比當前元素多一個。
重複第2步和第3步，直到最後。

來源

2013-12-18 17:20:32

，它對'下一個元素小於當前元素'檢查不起作用。我認爲你的意思是'如果當前元素小於下一個元素1或下一個元素1多於當前元素' –

@JasdeepSingh你不認爲[1,2,1]是連續序列嗎？ –

根據我對'[1,2,1]'中連續數字的理解，只有'[1,2]'是連續的。 –

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 - 方法：它會導致項目被丟棄。

來源

2013-12-18 17:37:08 steenslag

很酷（+1）。作爲獎勵，它不會不必要地計算實際的序列。 –

@undur_gongor ehmm，它確實... – steenslag

是的，但不是立即形式'[6，7，8]'。它是'[[6,7]，[7,8]]'。 –

我會做如下使用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

來源

2013-12-18 18:20:45

計數連續的整數元素的數目在給定我有一個陣列，例如如下的陣列

回答

相關問題