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


  • 0
    E

    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;
        }
    };
    

Log in to reply
 

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