lintcode 198. Permutation Index

用hash来记录出现的重复次数，是针对于所有元素的，不仅仅是小于。
http://www.mamicode.com/info-detail-1102985.html

class Solution {
public:
    /**
     * @param A: An array of integers
     * @return: A long integer
     */
    long long permutationIndexII(vector<int> &A) {
        // write your code here
        if(A.empty()) return 0;
        long long index = 1;
        long long factor = fact(A.size() - 1);
        for(int i = 0; i < A.size(); i++){
            int count = 0;
            unordered_map<int, int> hash;
            hash[A[i]]++;
            for(int j = i+1; j < A.size(); j++){
                if(A[j] < A[i]){
                    count++;
                }
                hash[A[j]]++;
            }
            int n = A.size() - i - 2;
            cout<<count<<" "<<n<<endl;
            index += count * factor / helper(hash);
            
            if(i <( A.size() - 1)) factor = fact(n);
        }
        return index;
        
    }
private:
    long long helper(unordered_map<int, int>& hash){
        long long factor = 1;
        
        for(auto iter = hash.begin(); iter != hash.end(); iter++){
            
            factor *= fact(iter->second);
        }
        cout<<factor<<endl;
        return factor;
    }
    long long fact(int n){
        long long factor = 1;
        while(n){
            factor *= n;
            n--;
        }
        return factor;
    }
};