47. Permutations II 전체 배열 반복

1580 단어
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example, [1,1,2] have the following unique permutations: [ [1,1,2], [1,2,1], [2,1,1] ]

생각:


이 문제는 이전의 Permutations 전체 배열의 연장이다. 입력 수조에 중복 숫자가 나타날 수 있기 때문에 이전의 알고리즘에 따라 연산하면 중복 배열이 발생한다. 우리는 중복 발생을 피해야 한다. 귀속 함수에서 앞의 수와 현재의 수가 같은지 아닌지를 판단해야 한다. 만약에 같다면 앞의 수는 이미 사용되어야 한다. 즉, 대응하는visited의 값이 1이어야 현재의 숫자를 사용할 수 있다.그렇지 않으면 다음 코드와 같이 중복 정렬이 발생하지 않도록 건너뛰어야 합니다.
 var permute = function(nums) {
            var res = [];
            var out = [];
            var visited = [];
            nums.sort((a,b)=>a-b)
            for (var i = 0; i < nums.length; i++) {
                visited[i] = 0;
            }
            permuteDFS(nums, 0, out, res, visited);
            return res;

            function permuteDFS(nums, pos, out, res, visited) {
                var tmp = out.concat();
                if (pos === nums.length) res.push(tmp);
                else {
                    for (var i = 0; i < nums.length; i++) {
                        if (visited[i] === 0) {
                            if(i>0 && nums[i]===nums[i-1] && visited[i-1]==0) continue;
                            visited[i] = 1;
                            out.push(nums[i]);
                            permuteDFS(nums, pos + 1, out, res, visited);
                            out.pop();
                            visited[i] = 0;
                        }
                    }
                }

            }
        };

좋은 웹페이지 즐겨찾기