My AC code(-_-, so many excpetional case need to care)


  • 0
    Z
        struct item__{
            int j;
            int base;
            item__(int x, int y):j(x),base(y){}
        };
        bool lessofitem(const item__ &x, const item__ &y)
        {
            return x.j>y.j?true:(x.j==y.j?(x.base>y.base?true:false):false);
        }
        class Solution {
            void swapone(vector<int>& nums, int begin, int end)//[]
            {
                nums[begin] = nums[begin] ^ nums[end] ;
                nums[end] = nums[begin] ^ nums[end] ;
                nums[begin] = nums[begin] ^ nums[end] ;
            }
            void swap(vector<int>& nums, int begin, int end)
            {
                while(begin<end)
                {
                    swapone(nums,begin,end);
                    ++begin,--end;
                }
            }
        public:
            void nextPermutation(vector<int>& nums) {
                if(nums.size()<2)return;
                int n = nums.size();int j,base;
                vector<item__>vc;// choose all seq like "123", 2 <3, index is 1-2, and 1<3 too, index is 0-2
     //get all index and put into vector<item__>vc
                for( base = n-1;base>=1;--base)
                {
                    for(j = base-1;j>=0;--j)
                    {
                        if(nums[j]<nums[base])
                        {
                            vc.push_back(item__(j,base));
                            break;
                        }
                        
                    }
                }
    
                if(vc.size()>0)
                {// if not empty, we should choose the j and base which value is biggest( so it will lead the NEXT bigger number )
    /// sort the vector, to get the BIGGEST j and base.
                    sort(vc.begin(),vc.end(),lessofitem);
    /// 1 ; swap number at j and at base
                    swapone(nums,vc[0].j,vc[0].base);
    //2 sort all others from j-1 to end
                    sort(nums.begin()+vc[0].j+1,nums.end());
                }
                else
    // if empty, means all number is bigger than the right side one, so just reverse it
                swap(nums,0,n-1);
                
                
            }
        };

Log in to reply
 

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