文档章节

lintcode-197 排列序号

a_xianyu
 a_xianyu
发布于 2017/08/09 22:10
字数 673
阅读 28
收藏 0

    原题连接:http://www.lintcode.com/zh-cn/problem/permutation-index/

排列序号 

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

样例

    例如,排列 [1,2,4] 是第 1 个排列。

/**
 * @create 2017-08-03 9:57
 */
public class Main {
    public static long permutationIndex(int[] A) {
        // write your code here
        int tag[] = new int[A.length]; //0表示没有计算过,1表示已经计算
        long result = 0;

        for (int i = 0; i < A.length - 1; i++) {
            int small = 0;
            for (int j = 0; j < A.length; j++) {
                if (A[j] < A[i] && tag[j] == 1) {
                    small++;
                }
            }
            tag[i] = 1;
            result = result + (position(A, A[i]) - small) * f(A.length - i - 1);
        }

        result++; //最后一位直接加1
        return result;
    }

    public static long f(int n) {
        long result = 1;

        for (int i = 1; i <= n; i++) {
            result *= i;
        }

        return result;
    }

    public static int position(int[] A, int target) {
        //从0开始
        int result = 0;

        for (int i = 0; i < A.length; i++) {
            if (A[i] < target)  {
                result++;
            }
        }

        return result;
    }

    public static void main(String[] args){
        int[] A = {3, 4, 2, 1};
        System.out.println(permutationIndex(A));
    }
}

    函数f(int) 用于计算阶乘,position(int[], int)用于返回某个数在其有序数组中的下标。

    ps: 如果只是求某个数在其有序数组中的下标,可以使用快排的思想,此时时间复杂度为O(log(n)), 但快排会改变原来数组中数的位置,如果新创建一个数组复制原来的值,则复杂度又会变为O(n).

    对于{3,4, 2, 1},先创建一个tag数组,默认值均为0. 然后进入外层for循环。此时内层的for循环由于条件不满足,什么也不做,small = 0(small表示比A[i]小的元素的个数), 只是令tag[0]=1,表示3这个元素已经访问过。然后计算result = result + (position(A, 3) - 0) * f(4 - 0 - 1) = 0 + (2 - 0)*(3!) = 12. 接下来 result = result + (position(A, 4) - 1) * f(4-1-1) = 12 + (3-1)*(2!)=16, result = result + (position(A, 2) - 0) * f(4-2-1)=16+(1-0)*(1!)=17, 最后一个数不需要进行计算,直接加1即可。

    其实理解也不难。

         (1,2,3,4), (1,2,4,3), (1,3,2,4), (1,3,4,2), (1,4,2,3), (1,4,3,2)

         (2,1,3,4), (2,1,4,3), (2,3,1,4), (2,3,4,1), (2,4,1,3), (2,3,3,1)

         (3,1,2,4), (3,1,4,2), (3,2,1,4), (3,2,4,1), (3,4,1,2), (3,4,2,1)

     .....

    对于{3,4,2,1}中的第一个3, 排在它前面的有12个数,也就是使比它小的数的个数2*(A.length-1)! = 12, 对于第二个4,从首位数字为3开始算它的位置。其实就相当于去掉数字3,计算{4,2,1},重复上述步骤。由于3比4小,去掉3后会影响4在{3,4,2,1}中的位置,所以small=1。(如果去掉的第一个数比4大,则不影响其去掉后4在新的有序数组中的位置)。所以(position(A, A[i]) - small) * f(A.length - i - 1)=(3-1)*f(4-1-1)=4, 剩下同理。

© 著作权归作者所有

a_xianyu
粉丝 0
博文 36
码字总数 18533
作品 0
哈尔滨
程序员
私信 提问
LintCode使用全解|如何高效提升算法和数据结构水平?

对于IT领域的求职者来说,通过刷题提升自己的编程能力是非常有必要的。在线评测平台 LintCode,整合了当前各大IT企业技术求职的热门题库,拥有2000多道常见面试题。可有效提升你的算法与数据...

2019/07/12
0
0
[LeetCode] Search a 2D Matrix II 搜索一个二维矩阵之二

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties: Integers in each row are sorted in ascending from left to ri......

群星纪元
2019/04/17
1
0
[原创]web报表开发技术专题一:序号问题

近期因为专注于用 c# 实现 web 报表,积累了一些经验和心得,也写过一篇介绍文章 , 也有网友提出没有说清楚。现觉得想用单篇文章来说明 web 报表开发难免会大而空,落不到实处。因而便想到每...

长平狐
2012/10/11
80
0
数组中最大的差值-LintCode

给 m 个数组, 每一个数组均为升序. 现在你可以从两个不同的数组中挑选两个整数(每一个数组选一个)并且计算差值. 我们将两个整数 a 和 b 之间的差定义为它们的绝对差 |a - b|. 你的任务是去找...

zhaohengchuan
2017/12/13
0
0
小朋友学奥数(21):康托展开

一、康托展开运算 把一个整数X展开成如下形式: X = an (n - 1)! + an-1 (n - 2)! + ... + ai (i - 1)! + ... + 2 1! + a1 * 0! 其中,ai为整数,并且0 <= ai < i,1 <= i <= n)。 ai表示原数......

海天一树X
2018/10/24
0
0

没有更多内容

加载失败,请刷新页面

加载更多

工作自由--2020年开篇,开启一个项目:工作自由 worksolo.cn

新年伊始,我突发奇想,也是很多人敢想而不敢做的事情,下面我以一个多年软件开发从业者的角度去思考,去设计这个项目,当然希望看到这篇文章的你可以给我更多思路: 项目名称:工作自由 域名...

_aron_
25分钟前
25
0
王道 第一章 计算机系统概述

这门课学的是逻辑实现,不是具体的机型 主要内容: 基本部件的结构和组织方式 基本运算的操作原理 基本部件和单元的设计思想 处理器+内存=计算机 存储器 存储器(高速缓存、主存储器、虚拟存...

heronos
今天
81
0
SpringBoot+Mybatis+Thymeleaf-Build Blog site_1

1、快速构建Springboot项目 (1)、 Spring Boot 项目目录结构介绍 (2)、 Spring Boot 项目启动的几种方式 2、 (1)、hello blog (2)、 DispatchServlet 配置 (3)、 静态 web 资源如何...

杨木发
今天
128
0
关于docker0: iptables: No chain/target/match by that name的问题解决

由于Docker 0默认网桥的iptables策略冲突问题,将导致一些web server启动时出现如下错误: docker: Error response from daemon: driver failed programming external connectivity on endpo......

王焱君
今天
103
0
js 下载 canvas 兼容移动端

很蛋疼的问题PC上好好的, 移动端下载不了 , 貌似前端 js 生成的时 base64 格式的 图片数据,移动端无法直接下载, 但是chrome 移动端和pc端都没问题, 国产的几个浏览器全部挂了 之前的下载方式...

阿豪boy
昨天
96
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部