lintcode198. 排列序号II

旧城等待， 2023-07-07 05:56 8阅读 0赞

给出一个可能包含重复数字的排列，求这些数字的所有排列按字典序排序后该排列在其中的编号。编号从1开始。

样例
    样例 1:
    
    输入:[1,4,2,2]
    输出:3
    样例 2:
    
    输入 :[1,6,5,3,1]
    输出:24

思路:与排列序号1相比，多了重复数字的可能性，所以我们在 lintcode-197-排列序号 的基础上，使用哈希表保存元素出现的次数，对于重复元素 A\[i\]，A\[i\] 在 \[0,i\] 区间中有重复元素，则用 A\[i\] 的 count \* fact 的结果除以重复次数 dup 的阶乘。

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 res=1;
            long long factor=1;
            int len=A.size();
            map<int,int> maps;
            long long dup=1;
            for (int i = len-1; i >=0 ; i--) {
        
                maps[A[i]]++;
                if(maps[A[i]]>1)
                    dup*=maps[A[i]];
                int cnt=0;
                for (int j = i+1; j < len; j++) {
        
                    if(A[j]<A[i]) cnt++;
                }
                res+=cnt*factor/dup;
                factor*=(len-i);
            }
            return res;
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，8人围观）

还没有评论，来说两句吧...

相关阅读

相关 47. 全排列 II

> 关上过去和未来的铁门，活在“今天”这个舱室中。——《人性的优点》 47. 全排列 II 给定一个可包含重复数字的序列 nums ，按任意顺序返回所有不重复的全排列

系统管理员/ 2024年03月31日 14:52/ 0 赞/ 105 阅读

相关 47.全排列 II

47.全排列 II 题干描述解题思路拓展总结代码实现题干描述 [力扣入口][Link 1] 给定一个可包含重复数字的序列

男娘i/ 2023年10月16日 14:09/ 0 赞/ 34 阅读

相关 lintcode 125. 背包问题 II

有 n 个物品和一个大小为 m 的背包. 给定数组 A 表示每个物品的大小和数组 V 表示每个物品的价值.问最多能装入背包的总价值是多大? 样例样例 1:

比眉伴天荒/ 2023年07月07日 12:38/ 0 赞/ 53 阅读

相关 lintcode198. 排列序号II

给出一个可能包含重复数字的排列，求这些数字的所有排列按字典序排序后该排列在其中的编号。编号从1开始。样例样例 1: 输入:[1,4,2,

旧城等待，/ 2023年07月07日 05:56/ 0 赞/ 9 阅读

相关 Permutations II（C++全排列 II）

（1）递归 class Solution { private: vector<vector<int>> v; public:

ゝ一纸荒年。/ 2022年10月11日 00:44/ 0 赞/ 174 阅读

相关 lintcode Permutation Index 排列序号

排列序号 [ 描述][Link 1] [ 笔记][Link 2] [ 数据][Link 3] [ 评测][Link 4] 给出一个不含重复数字

灰太狼/ 2022年07月15日 02:37/ 0 赞/ 161 阅读

相关下一个排列 lintcode

下一个排列 [ 描述][Link 1] [ 笔记][Link 2] [ 数据][Link 3] [ 评测][Link 4] 给定一个

古城微笑少年丶/ 2022年07月15日 00:46/ 0 赞/ 171 阅读

相关 lintcode之排列问题

1/ 子集给定一个含不同整数的集合，返回其所有的子集注意事项子集中的元素排列必须是非降序的，解集必须不包含重复的子集您在真实的面试中是否遇到过这个题

爱被打了一巴掌/ 2022年07月14日 11:17/ 0 赞/ 160 阅读

相关 LintCode -- 合并排序数组 II

描述合并两个排序的整数数组A和B变成一个新的数组。样例给出A=\[1,2,3,4\]，B=\[2,4,5,6\]，返回 \[1,2,2,3,4,4,5,6\

朴灿烈づ我的快乐病毒、/ 2022年05月25日 11:12/ 0 赞/ 192 阅读

相关 Lintcode: Sort Colors II 解题报告

[Sort Colors II ][Sort Colors II] 原题链接： [http://lintcode.com/zh-cn/problem/sort-color

柔光的暖阳◎/ 2022年04月22日 15:26/ 0 赞/ 194 阅读