# Find an interesting law, present a really innovative solution with 9ms c++ and beating 81.98%

• Every number has a 'direction valuable'(next number or previous).
Active number is a number that is bigger than its directive neighbor.
My algorithm is by this step:
1 sort nums from small to big, and set direction valuable of each number '-1'(direct previous).
2 repeat this step:
(1)Find the biggest active number k.
(2)Swap k and its directive neighbor.
(3)Alter the directive valuable of each number bigger than k.
3 Till we can't find any active number.

``````class Solution {
public:
vector<vector<int>> permute(vector<int>& nums) {
vector<vector<int> >res;
if(nums.size()<1)return res;
sort(nums.begin(),nums.end());
res.push_back(nums);
map<int,int>hash;
int k=-1;
while((k=get(k,nums,hash))!=-1){
int t=nums[k];int k2=hash[nums[k]]+k;
nums[k]=nums[k2];nums[k2]=t;k=k2;
res.push_back(nums);

}
return res;
}

int get(int k_old,vector<int>& nums,map<int,int>&hash){
int k=-1;
for(int i=0;i<nums.size();i++){
if(k_old==-1)hash.insert(pair<int,int>(nums[i],-1));
else{
if(nums[i]>nums[k_old])hash[nums[i]]*=-1;
int p=hash[nums[i]]+i;
if(p<0||p>=nums.size())continue;
if((k==-1||nums[i]>nums[k])&&nums[i]>nums[p])k=i;
}
}
if(k_old==-1&&nums.size()>1)k=nums.size()-1;
return k;
}
};
``````

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