java数据结构与算法刷题目录(剑指Offer、LeetCode、ACM)-----主目录-----持续更新(进不去说明我没写完):https://blog.csdn.net/grd_java/article/details/123063846
此题为46题的衍生题,在46题的基础上,加上了是否重复的判断,除此之外完全一样。
🏆LeetCode46. 全排列https://blog.csdn.net/grd_java/article/details/136683863
1. 暴力回溯
解题思路:时间复杂度O( n n n^n n n ),但是严格来说只到了O( n ∗ n ! n*n! n ∗ n ! )。空间复杂度O(n)
在46题的基础上增加一些判断是否重复的操作 首先我们先将数组排序,这样我们就能通过两个相邻值的比较,确定当前值是否是一个重复的值(不止一个它) 我们进行全排列时,每个位置可以选择任何不同的值,但是现在有重复的值,就必须确保同一个位置,重复的值只选一次 所以进行全排列时,通过比较相邻的值就可以判断了。但是必须是有序数组才行(重复数字会都挨在一起)
int [ ] nums; boolean [ ] numsFlag; int len; List < List < Integer > > ans = new ArrayList < List < Integer > > ( ) ; public List < List < Integer > > permuteUnique ( int [ ] nums) { Arrays . sort ( nums) ; this . nums = nums; this . len = nums. length; this . numsFlag = new boolean [ len] ; ArrayList < Integer > records = new ArrayList < > ( ) ; backTracking ( records) ; return ans; } public void backTracking ( List < Integer > records) { if ( records. size ( ) == len) ans. add ( new ArrayList < > ( records) ) ; else { for ( int i = 0 ; i< len; i++ ) { if ( this . numsFlag[ i] == true || ( i> 0 && nums[ i] == nums[ i- 1 ] && this . numsFlag[ i- 1 ] == false ) ) continue ; this . numsFlag[ i] = true ; records. add ( nums[ i] ) ; backTracking ( records) ; this . numsFlag[ i] = false ; records. remove ( records. size ( ) - 1 ) ; } } }
2. 分区法+回溯
解题思路:时间复杂度O( n ∗ n ! ∗ l o g 2 n n*n!*log_2{n} n ∗ n ! ∗ l o g 2 n ),其中 l o g 2 n log_2{n} l o g 2 n 是判断是否重复的时间开销。空间复杂度O(n)
含有重复的元素序列,进行全排列,这个方法就不太好用,因为处理重复很麻烦 所以这里只能通过笨办法,每次选择数字判断是否重复时,从当前位置可选值中,依次遍历判断我们当前要选的数字是否之前就存在过 这个算法依然不需要flag数组标志数字是否已经选择过,也不需要事先排序。 与46题代码几乎完全照搬,只单纯加了一个循环遍历数组,判断是否重复的方法而已。
class Solution { int [ ] nums; int len; List < List < Integer > > ans = new ArrayList < List < Integer > > ( ) ; public List < List < Integer > > permuteUnique ( int [ ] nums) { this . nums = nums; this . len = nums. length; dfs ( 0 ) ; return ans; } private void dfs ( int idx) { if ( idx == len) { List < Integer > result = new ArrayList < > ( ) ; for ( int num: nums) result. add ( num) ; ans. add ( result) ; } for ( int i = idx; i < len; i++ ) { if ( isRepeat ( nums, idx, i) ) continue ; swap ( nums, idx, i) ; dfs ( idx + 1 ) ; swap ( nums, idx, i) ; } } private boolean isRepeat ( int [ ] nums, int idx, int i) { while ( idx < i) if ( nums[ idx++ ] == nums[ i] ) return true ; return false ; } private void swap ( int [ ] nums, int i, int j) { int tmp = nums[ i] ; nums[ i] = nums[ j] ; nums[ j] = tmp; }
}