First reaction
How do I feel like I've done similar problems.
Compare with question 31 "next arrangement"
The next permutation of an array of integers refers to the next lexicographically ordered permutation of its integers. More formally, if all permutations of an array are arranged in a container from small to large according to their dictionary order, Then the next arrangement of the array is the one behind it in this ordered container. If there is no next larger permutation, the array must be rearranged to the least lexicographically ordered permutation (That is, its elements are arranged in ascending order). Example 1: Input: nums = [1,2,3] Output:[1,3,2]
By calling this repeatedly, you can actually get each arrangement. However, such efficiency is too low.
If you use a method similar to recursion, take a number from the remaining array and add it to the header each time, and then use this method for the remaining array, so that you can recursively find out each remaining permutation and combination. The space complexity should also be O(n^2). This method is similar to guangsearch
java knowledge
This is a big hole
List<String> list2 =
new ArrayList<String>(Arrays.asList("apple", "banana", "orange"));
be careful:
- Applies to object arrays (such as String), not arrays of basic data types (such as Integer)
- The target array and the obtained list will be interrelated, and one change will affect the other
- add(), remove(), clear() and other methods are not supported, because the obtained list and the variable length list are not from the same package. If you want to modify the list, it's better to use a loop to put the values in the array into the list one by one
Collate from https://blog.csdn.net/kzadmxz/article/details/80394351
Submit and pass
It's really troublesome. There are several pits
Delete elements from the list, pass the list as a parameter, traverse the list, convert array to list, and a pile of pits.
class Solution {
public List<List<Integer>> permute(int[] nums) {
List<Integer> end = arrayToList(nums);
List<List<Integer>> ans = new ArrayList<>();
ans = bfs(ans, new ArrayList<>(), end);
return ans;
}
public List<List<Integer>> bfs(List<List<Integer>> ans , List<Integer> head , List<Integer> end){
if(end.size() == 1){
List<Integer> headNew = copyList(head);
for(int value:end){
headNew.add(value);
}
ans.add(headNew);
return ans;
}
for(int value:end){
List<Integer> headNew = copyList(head);
List<Integer> endNew = copyList(end);
headNew.add(value);
removeValue(endNew, value);
ans = bfs(ans, headNew, endNew);
}
return ans;
}
public List<Integer> arrayToList(int[] nums){
List<Integer> end = new ArrayList<Integer>();
for(int i = 0 ; i < nums.length ; i ++){
end.add(nums[i]);
}
return end;
}
public List<Integer> copyList(List<Integer> org){
List<Integer> ans = new ArrayList<>();
for(int value:org){
ans.add(value);
}
return ans;
}
public void removeValue(List<Integer> list, int target){
for(int i = 0, len = list.size(); i < len; i++){
if(list.get(i) == target){
list.remove(i);
len--;//list length reduction
i--;//After the list is deleted, the right data moves to the left, and the current subscript needs to be checked again
}
}
}
}
Next question
There is one more repeatable condition
First reaction
Forget it. I thought the method in question 31 would timeout. It's wrong again. The time complexity of the method in question 31 is O(n), because it doesn't even need to be sorted. In this way, it's OK to call it directly in a loop.
If you change it on the basis of question 46, it is mainly to change i + + to find the next different number.
But I'll try to change 31 questions
Submit and pass
Unexpectedly, when I changed the code of question 31 above, I found that I was not only lazy and wasted performance with the sort method, but also covered up a serious bug (because it was covered up by sort) because I didn't pay attention to the latter half of the array
But now it's fixed. The nextPermutation function in the second half of the paragraph has no problem with question 31. It's also 0ms
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
ans.add(arrayToList(nums));
while(nextPermutation(nums)){
ans.add(arrayToList(nums));
}
return ans;
}
public boolean nextPermutation(int[] nums) {
if(nums.length == 1){
return false;
}
// Find the first number that is not increasing from back to front
int i = nums.length-2;
int max = nums[nums.length-1];
for( ; i >= 0 ; i --){
if( nums[i] < max){
break;
}else if(nums[i] > max){
max = nums[i];
}
}
if(i == -1){
for(int j = 0 ; j < nums.length/2 ; j ++){
int temp = nums[j];
nums[j] = nums[nums.length-1 - j];
nums[nums.length-1 - j] = temp;
}
return false;
}
//Find a number greater than nums[i] and closest to nums[i]
int minDiff = 1000;
int minDiffIndex = -1;
//Since the latter half of the array is considered to be arranged in descending order from left to right, after finding the target number and transposing, the array should be kept descending from left to right
//In consideration of the possibility that several consecutive numbers are the same, in order to ensure the decrement, the num [J] - num [i] < mindiff should be changed to < = (or check from right to left)
//You can also cut branches here
for(int j = i+1 ; j < nums.length ; j ++ ){
if(nums[j] > nums[i] && nums[j] - nums[i] <= minDiff){
minDiff = nums[j] - nums[i];
minDiffIndex = j;
}
}
//Exchange numbers of mindiffendex and i position
int t = nums[minDiffIndex];
nums[minDiffIndex] = nums[i];
nums[i] = t;
// System.out.println("i+1 = " + (i+1) + " ; nums.length-1 = " +( nums.length-1));
// for(int k = 0 ; k < nums.length ; k ++){
// System.out.print(nums[k] + " ");
// }
if((nums.length-1) > i+1 ){
for(int j = i+1 ; j <= (nums.length-1 + (i+1))/2 ; j ++){
int temp = nums[j];
nums[j] = nums[nums.length-1 - (j - (i+1))];
nums[nums.length-1 - (j - (i+1))] = temp;
}
}
return true;
}
public List<Integer> arrayToList(int[] nums){
List<Integer> end = new ArrayList<Integer>();
for(int i = 0 ; i < nums.length ; i ++){
end.add(nums[i]);
}
return end;
}
}