2016-03-14 1 views
1

我正在編寫一個函數來壓扁嵌套數組(Python list)。例如將[1,2,[3]]變成[1,2,3],[[1,2,[3]],4]變成[1,2,3,4]等。當存在遞歸時保留局部變量的當前值

I有以下幾點:

def flatten_array(array): 
    flattened_array = [] 
    for item in array: 
     if not isinstance(item, list): 
      flattened_array.append(item) 
     else: 
      flatten_array(item) 
    return flattened_array 

所以這個想法是讓函數遞歸,以處理嵌套到未知深度的情況。我的問題是flattened_array每次遇到嵌套列表時都會重新初始化(當遞歸調用flatten_array時)。

print flatten_array([1,2,[3]]) 
[1,2] 

如何在遞歸調用時保持flattened_array的狀態?

回答

3

更改線路

else: 
    flatten_array(item) 

else: 
    flattened_array+=flatten_array(item) 

所以全功能讀起來就像

def flatten_array(array): 
    flattened_array = [] 
    for item in array: 
     if not isinstance(item, list): 
      flattened_array.append(item) 
     else: 
      flattened_array+=flatten_array(item) 
    return flattened_array 

這給

flatten_array([1,2,[3]]) # [1,2,3] 
flatten_array([1,2,[3,[4,5]]]) # [1,2,3,4,5] 
flatten_array([1,2,[3,[4,5]],6,7,[8]]) # [1,2,3,4,5,6,7,8] 

您的原始代碼對遞歸調用沒有做任何事情。你回到列表中的結果,但只是丟棄它。我們想要做的是將其附加到現有列表的末尾。


此外,如果你不想讓創建臨時數組,我們可以創建一個數組,第一次調用該函數,只是追加到它。

def flatten_array(array,flattened_array=None): 
    if flattened_array is None: 
     flattened_array = [] 
    for item in array: 
     if not isinstance(item,list): 
      flattened_array.append(item) 
     else: 
      flatten_array(item,flattened_array) 
    return flattened_array 

這個版本的結果是相同的,並且可以使用相同的方式,但在原來的,每次調用函數創建一個新的空數組的工作。通常這不是問題,但取決於深度或子陣列的大小,這可以建立在內存中。

此版本將數組變爲給定數組。當僅用輸入(如flatten_array([1,2,[3]]))調用它時,它會創建一個空數組來處理,否則它只會添加到給定數組(因此遞歸調用只需要給該數組添加),並對其進行修改。

這有允許您添加到,如果我們想要一個現有陣列的優勢:

a = [1,2,3] 
b = [2,3,[4]] # we want to add flatten this to the end of a 
flatten_array(b,a) # we don't bother catching the return result here 
print(a) # [1,2,3,2,3,4] 


這裏有一個微妙的一點。您可能會問,爲什麼我們沒有將函數定義爲 def flatten_array(array,flattened_array=[]),並在函數內部獲得乾燥的測試。嘗試一下並調用該函數幾次。會發生什麼情況是,在函數定義時會創建一次默認值,而不是每次調用該函數時。這意味着就地修改的默認數組由每個函數調用共享,從而累積結果。

這可能不是我們想要的。通過將默認值設置爲None並每次在函數內創建一個新的空數組,我們確保每次調用該函數都有一個唯一的空數組來處理。

+0

謝謝。不知道可以使用'+'運算符來追加到列表。 – Pyderman

+1

@Pyderman它並不完全追加。它將兩個列表合併在一起。如果你想添加一個項目到列表中,你需要使用append方法,但是如果你有兩個列表,並且你想將其中一個添加到另一個列表的末尾,你可以添加它們。請注意,如果你已經學習了很多代數,這是一個非交換加法的例子。 – Matthew

+0

@Matthew感謝您的補充闡述和替代解決方案。 – Pyderman