share O(nK) solution using Java with some explanation !


  • 1
    T

    Here we have two arrays:
    one is res[k],which denotes the number of k inverse pairs given a new element!
    another is sum[k],which denotes the number of <=k inverse pairs given a new elements.
    Then, we can use a for loop to iterate n-times to get final result, basically the core relation between res and sum is : res[j]=sum[j]-sum[j-i] if j-i>=0, else res[j] is simply equal to sum[j] given a new element has been considered, where i is 1<=i<=n, and j is i<=j<=k. Hope it helps!
    More specifically, suppose we have calculated 1,2,3,4,5,6,7 elements' res and sum array. Then, after the next step, the 8 comes in. Now, as for every k, we will consider each of {8-k, 8-k+1,8-k+2,...8} as the last element to form k inverse pairs' array, that's why will have res[k]=sum[k]-sum[k-8] if k-8>=0, or res[k]=sum[k] if k<8.

    More details:
    It means that if k=4, then we will consider {1,2,3,4,5,6,7,8}, {1,2,3,4,5,6,8,7},{1,2,3,4,5,7,8,6}, {1,2,3,4,6,7,8,5} and {1,2,3,5,6,7,8,4} cases. As for every case, we need to fix the last element, and then focus on all the permutations of previous 7 elements. Since we already calculated res and sum for the previous step(I mean the step for only having 7 elements), so we can just retrieve information directly from res and sum and update their values.

    public class Solution {
        public int kInversePairs(int n, int k) {
             long mod=(long)(1e9+7);
             
             long[] res=new long[k+1];
             long[] sum=new long[k+1];
             res[0]=1;
             Arrays.fill(sum,1);
             
             for(int i=2;i<=n;i++){
                //long[] temp=sum.clone();
                for(int j=0;j<=k;j++){
                    if(j==0){
                        res[0]=1;
                    }else{
                        res[j]=(j-i)>=0 ? ((sum[j]-sum[j-i]+mod)%mod) : ((sum[j]+mod)%mod);
                    }
                }
                
                for(int j=1;j<=k;j++){
                    sum[j]=(res[j]+sum[j-1]+mod)%mod;
                }
             }
             
             return (int)res[k];
        }
    }
    

  • 0
    F

    @tiandiao123 said in share O(nK) solution using Java with some explanation !:

    we will consider each of {8-k, 8-k+1,8-k+2,...8} as the last element to form k inverse pairs' array

    What do you mean by we will consider each of {8-k, 8-k+1,8-k+2,...8} as the last element to form k inverse pairs' array?


  • 1
    T

    It means that if k=4, then we will consider {1,2,3,4,5,6,7,8}, {1,2,3,4,5,6,8,7},{1,2,3,4,5,7,8,6}, {1,2,3,4,6,7,8,5} and {1,2,3,5,6,7,8,4} cases. As for every case, we need to fix the last element, and then focus on all the permutations of previous 7 elements. Since we already calculated res and sum for the previous step(I mean the step for only having 7 elements), so we can just retrieve information directly from res and sum and update their values.
    Sorry, my description is a little confusing. Hope it helps.


Log in to reply
 

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