Swap version java


  • 0
    C
    public class Solution {
        public List<List<Integer>> permuteUnique(int[] nums) {
            Arrays.sort(nums);
            List<List<Integer>> res = new ArrayList<>();
            if(nums == null|| nums.length == 0) res.add(new ArrayList<Integer>());
            helper(res, nums, 0);
            return res;
        }
        private void helper(List<List<Integer>> res, int[] nums, int index){
            if(index == nums.length){
                List<Integer> list = new ArrayList<>();
                for(int num : nums){
                    list.add(num);
                }
                res.add(list);
                return;
            }
            for(int i = index; i < nums.length; i++ ){
                if(i > index && nums[i] == nums[index]) continue;
                swap(nums, index, i);
                helper(res, Arrays.copyOf(nums, nums.length), index+1);
            }
        }
        private void swap(int[] a, int i , int j){
            int tmp = a[i];
            a[i] = a[j];
            a[j] = tmp;
        }
    }
    

  • 0
    M

    A quick note. You don't have to sort the array initially if you swap index and i again inside the for loop after calling the helper function.

    for(int i = index; i < nums.length; i++ ){
                if(i > index && nums[i] == nums[index]) continue;
                swap(nums, index, i);
                helper(res, Arrays.copyOf(nums, nums.length), index+1);
                swap(nums,index,i);
            }
    

    This happens because the if statement doesn't swap index and i if both have the same value. After the swap the value of index and i changes. So if you swap the values again you will not be repeating the numbers.


  • 0
    D

    said in Swap version java:

    helper(res, Arrays.copyOf(nums, nums.length), index+1);

    Can you please explain this code? I am not able to understand:

    1. Why you do a Arrays.copyOf()?
    2. Why swap(nums,index,i) is not called again

  • 0
    M

    @dev.abkulkar
    Let me try to sum up it the best I can:

    1. He does arrays.copyOf so that he can create a new instance of the array and pass it. The question is why do we have to create a new array? It's because when helper is called again and again it will completely change the positions of all the variable. But when you use copyOf only the two values that you changed will be changed. Any further action taken on the array will be done on a completely different copy of the array, so it doesn't affect the current instance of the array.
      This loops back to the concept of pass by reference. In Java, arrays are passed in as a reference. Any changes you make in any other place will be reflected back. But when you do copyOf, a new array is created with those values and a different reference is passed. So that any changes made in any other function will not be reflected back.
    2. swap is not called again in the original code because the array is initially sorted.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.