2018-04-02

算法分析第九题

数字填空 给定N个不同的整数以及一个包含n个空格的序列，每个空格之间事先给定有不等符号。请设计一个算法，将n个整数填入这n个空格中并满足不等号的约束。

例子：

空格： __ < __ > __ < __ < __
数字原序列：4，6，3，1，8
输入后的序列：1，8，3，4，6

老师课堂上说的的思路：

• 先排序
• 将最大值插入到第二个空格中
  排序代码：

        int[] a = {4,6,3,1,8};
        Arrays.sort(a);

插入代码：

        ArrayList<Integer> b = new ArrayList<Integer>();
        b.add(1,a[4]);

整体主要代码如下图：

1.png

但是！！！

这样的写法，很明显，是在已知了几个<>符号的位置，排列方式下完成的
我们能不能让用户来输入这些坑爹的符号，并且依然输出一个满足条件的序列呢？？
of course . 是可以滴：

思路：

• 依然先完成从小到大的排序
• 遍历，找“>”符号！！为什么要找它呢，因为它和我们的从小到大的序列冲突！！！
• 每找到一个> 符号，就把当前最大值插入到它的前面~，这样，不就多了一个数了吗？ 没关系，因为我们是从小到大排序好的，直接删除最后一个数就行了~
• 当前最大值，什么叫当前最大值？ 就是说，往前插入过的数，就不再是当前最大值啦~；
• 遍历一圈过后，新的序列就满足要求啦~输出就行了！

上代码：

2.png

样例输入 ：
/> < > >/
样例输出
8 > 1 < 6 > 4 > 3