LeetCode – Permutaciones II (Java)

Dada una colección de números que pueden contener duplicados, devuelve todas las posibles permutaciones únicas.

For example, [1,1,2] have the following unique permutations:
[1,1,2], [1,2,1], and [2,1,1].

Solución Java 1

Según la permutación, podemos agregar un conjunto para rastrear si un elemento está duplicado y no es necesario intercambiarlo.

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> result = new ArrayList<>();
    helper(0, nums, result);
    return result;
}
 
private void helper(int start, int[] nums, List<List<Integer>> result){
    if(start==nums.length-1){
        ArrayList<Integer> list = new ArrayList<>();
        for(int num: nums){
            list.add(num);
        }
        result.add(list);
        return;
    }
 
    HashSet<Integer> set = new HashSet<>();
 
    for(int i=start; i<nums.length; i++){
        if(set.contains(nums[i])){
            continue;
        }
        set.add(nums[i]);
 
        swap(nums, i, start);
        helper(start+1, nums, result);
        swap(nums, i, start);
    }
}
 
private void swap(int[] nums, int i, int j){
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

LeetCode - Número Palindrome (Java)

Solución Java 2

Use set para mantener la singularidad:

public static ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
	ArrayList<ArrayList<Integer>> returnList = new ArrayList<ArrayList<Integer>>();
	returnList.add(new ArrayList<Integer>());
 
	for (int i = 0; i < num.length; i++) {
		Set<ArrayList<Integer>> currentSet = new HashSet<ArrayList<Integer>>();
		for (List<Integer> l : returnList) {
			for (int j = 0; j < l.size() + 1; j++) {
				l.add(j, num[i]);
				ArrayList<Integer> T = new ArrayList<Integer>(l);
				l.remove(j);
				currentSet.add(T);
			}
		}
		returnList = new ArrayList<ArrayList<Integer>>(currentSet);
	}
 
	return returnList;
}

¡Gracias a Milán por una solución tan sencilla!

Artículos Relacionados:

Por Programación.Click

Deja una respuesta Cancelar la respuesta