查找具有重複項的數組的排列。爲什麼按遞歸值傳遞（C++實現）

有多種方法可以找到帶有重複項的整數數組的所有排列。這裏我只談論遞歸方法而不使用額外的「visited []」數組。查找具有重複項的數組的排列。爲什麼按遞歸值傳遞（C++實現）

做有正確的方法是：

void helper(vector<vector<int>>& ans, vector<int> nums, int pos) { 
     if(pos == nums.size()-1) { 
      ans.push_back(nums); 
      return; 
     } 
     for(int i = pos; i < nums.size(); i++) { 
      if(i == pos || nums[i] != nums[pos]) { 
       swap(nums[i], nums[pos]); 
       helper(ans, nums, pos+1); 
      } 
     } 
    } 
    vector<vector<int>> permuteUnique(vector<int>& nums) { 
     int n = nums.size(); 
     vector<vector<int>> ans; 
     sort(nums.begin(), nums.end()); 
     helper(ans, nums, 0); 
     return ans; 
    }

爲什麼它通過NUMS []作爲進入副本遞歸函數也不是那麼清晰。所以我環顧了一下geeks for geeks，它說：「這個想法是修復第一個索引處的第一個字符並遞歸調用其他後續索引」。我想我可以修復第一個字符，然後遞歸調用其他後續索引，方法是傳遞nums []作爲參考，並在遞歸完成時返回「swap back」（如下所示）。但不幸的是它沒有奏效。

void helper(vector<vector<int>>& ans, vector<int>& nums, int pos) { 
    if(pos == nums.size()-1) { 
     ans.push_back(nums); 
     return; 
    } 
    for(int i = pos; i < nums.size(); i++) { 
     if(i == pos || nums[i] != nums[i-1]) { 
      swap(nums[i], nums[pos]); 
      helper(ans, nums, pos+1); 
      swap(nums[i], nums[pos]); 
     } 
    } 
} 
vector<vector<int>> permuteUnique(vector<int>& nums) { 
    int n = nums.size(); 
    vector<vector<int>> ans; 
    sort(nums.begin(), nums.end()); 
    helper(ans, nums, 0); 
    return ans; 
}

我想知道什麼是錯誤的時候傳遞nums []作爲參考遞歸？爲什麼通過拷貝將nums []傳遞給遞歸是正確的？

來源

2017-07-29 John Tan

我想我找到了原因。按值傳遞和按參考傳遞給出了兩種完全不同的算法。瞭解這一點。我們首先注意兩個重要的觀察：1.我們做的第一件事是對數組進行排序，爲什麼？因爲我們希望所有的排列都以「下一個排列」順序，即123,132,213,231,312,321來訪問。2.下一個遞歸中的子問題也保持排序的屬性。 –

我想我找到了原因。按值傳遞和按參考傳遞給出了兩種完全不同的算法。瞭解這一點。首先我們來注意兩點：

我們做的第一件事是對數組進行排序，爲什麼？因爲我們希望以「下一個排列」順序來訪問所有排列，即123,132,213,231,312,321。所以不會有重複。
下一個遞歸的子問題也維護了排序的屬性。我們用一個例子來說明這一點。輸入NUMS = [1,2,2,3]通過由值來遞歸，與POS = 0，

I = 0：子問題是[2,2,3]，

I = 1：子問題是[1,2,3]，

I = 2：跳過，

I = 3的子問題是[1,2,2]。

這個遞歸級別的所有子問題都是SORTED。但是，如果[1,2,2,3]通過引用傳遞，則子問題不會排序，因此您無法在「下一個排列」方法上進行回覆，以便爲您提供非重複的排列。

如果你還在困惑，請花一些時間，通過討論閱讀： https://discuss.leetcode.com/topic/8831/a-simple-c-solution-in-only-20-lines/28?page=2

來源

2017-08-03 14:00:45

查找具有重複項的數組的排列。爲什麼按遞歸值傳遞（C++實現）

回答

相關問題