Next permutation of string given in a vector,dev-c++ gives output ([2,1]) for input [1,2] but OJ generates[2,0] pls help


  • 0
    H

    //compare function (utility function for qsort)

    int compare (const void* a,const void* b) {
    return ( (int)a - (int)b);
    }

    class Solution {
    public:
    void nextPermutation(vector<int> &num) {

        int len =num.size();
        int *arr;
        
        arr= new int[len];
        // copying elements given in vector form to array arr[]
        for (int i=0;i<len;i++)
            arr[i]=num[i];
            
        // finding next permutation of arr[]
        nextnum(arr,len);
        
        // copying back to vector
        for (int i=0;i<len;i++)
        	num[i]=arr[i];
    

    }

    void nextnum(int* arr,int size) {
        // initially start from 2nd last index
        int i=size-2;
        //store last element as pre
        int pre = arr[size-1];
        //find first element from right which is smaller than element at its right
        while (i>=0&&arr[i]>=pre){
            pre = arr[i];
            i--;
        }
        //if no found sort arr[] in asending order
        if (i==-1) {
            qsort((void*)arr,size,sizeof (int) ,compare);
            return ;
            
        }
        //if found
        else {
            //find ceilling from arr in its right-side of element found 
            int ceilling=i+1;
            for (int j=i+2;j<size;j++) 
                if (arr[j]>arr[i]&&arr[j]<arr[ceilling])
                    ceilling=j;
            //swap element with its ceil
            int temp=arr[i];
            arr[i]=arr[ceilling];
            arr[ceilling]=temp;
            //sort remaining arr in its right 
            qsort(arr+i+1,size-i,sizeof (int),compare);
                
        }
    }
    

    };


  • 0
    N

    Input [1,2], my code output [2,1]. But OJ output a Runtime Error! I don't know why?


Log in to reply
 

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