算法导论习题 9.1.1整型数组的次小值
证明：在最坏情况下，利用n+ceil(lgn)-2次比较，即可得到n个元素中的第2小元素。（提示：同时找最小元素）
补充说明：
(1)这里的比较是只元素之间的比较。下标的比较是不算在内的。
(2)ceil是向上取整的意思
1. 思路解析
1.1 总体思路解析
具体思路解析参照女神 windmissing 的解析，看完之后思路会很清晰，windmissing同时也给出了 python 和 c++版本的实现.
下面给出 java 版本的实现 以及 代码解析
1.2 代码思路分析
数据结构 : 二叉树 + 链表
为什么要使用链表呢?
-
解决这个问题需要在第一次遍历求最小值得时候,
从底向上建立一颗二叉树; 就拿 最后一层来说吧, 最后一层的成对(2个数)的数比较之后,会形成二叉树的 倒数第二层 , 如果只是简单的使用二叉树结构, 我该怎么遍历这一层呢? -
看来为了能在遍历
最后一层之后, 接着遍历倒数第二层, 迭代的建二叉树, 需要能遍历 倒数第二层, 在树的同一层,我们使用链表的结构,就能从头结点遍历的尾了. -
嗯, 看来这样就能在第一次遍历的求最小值得时候建立一棵树了, 为了在第二步求
次小值的时候简单一点, 你可以把树建成二叉搜索树(左孩子值 < 根节点值 < 右孩子值). 这样次小值就只会在最小值所在的 子树 右节点出现了.
2.代码实现
code
package chapter9;
/**
* Created by NowGood on 2017/3/4.
*/
public class Exercise911 {
/**
* head 当遍历某一层时, head 指向二叉树这一层的头结点, 当二叉树建立后, head 为树的根节点
* child 孩子节点
* parant 父节点; 两个孩子节点比较后,建立父节点 parent
* firstPoint 遍历链表时, 成对的两个中的第一个
* secondPoint 遍历链表时, 成对的两个中的第二个
*/
BinaryNode head;
BinaryNode child;
BinaryNode parent;
BinaryNode firstPoint;
BinaryNode secondPoint;
BinaryNode parentPoint;
/**
* 寻找最小元素, 建二叉树
*/
public int firstSmall(int[] arr) {
if (arr.length < 1 || arr == null)
throw new RuntimeException("No data");
if (arr.length == 1)
throw new RuntimeException("No second data");
head = new BinaryNode(arr[0]);
head.next = new BinaryNode(arr[1]);
// 第一次处理数组,由于输入数组是整型,和后续处理的BinaryNode类不同不同,故设置tag = 1
// 表示第一次处理, 并在第一次处理之后
int tag = 1;
while (head.next != null) {
if (tag == 1) {
for (int i = 0; i < arr.length; i += 2) {
// 1. 奇数个元素,通过最后一个孩子节点直接建立父节点
// 2. 将两个数中较大的赋值给左孩子节点
if (i == arr.length - 1) {
child = new BinaryNode(arr[i]);
parent = new BinaryNode(arr[i]);
parent.leftChild = child;
} else if (arr[i] < arr[i + 1]){
parent = new BinaryNode(arr[i]);
parent.leftChild = new BinaryNode(arr[i]);
parent.rightChild = new BinaryNode(arr[i+1]);
}else {
parent = new BinaryNode(arr[i + 1]);
parent.leftChild = new BinaryNode(arr[i + 1]);
parent.rightChild = new BinaryNode(arr[i]);
}
if (tag == 1) {
// 自相向上建树, 获得上一层链表的头元素
head = parent;
parentPoint = parent;
tag = 0;
} else {
// 建立链表
parentPoint.next = parent;
parentPoint = parent;
}
}
}
// 打印建二叉树的过程
BinaryNode x = head;
while (x != null) {
System.out.print(x.element + " ");
x = x.next;
}
System.out.println();
// 这里的处理过程和上面一样,只不过这里处理对象是 BinaryNode 链表, 上面是 int 数组
firstPoint = head;
head = null;
while (firstPoint != null) {
//secondPoint 两个元素比较中 指向第二个元素的指针
secondPoint = firstPoint.next;
if (secondPoint == null) {
parent = new BinaryNode(firstPoint.element);
parent.leftChild = firstPoint;
firstPoint = firstPoint.next;
} else if (firstPoint.element < secondPoint.element){
parent = new BinaryNode(firstPoint.element);
parent.leftChild = firstPoint;
parent.rightChild = secondPoint;
firstPoint = secondPoint.next;
}else {
parent = new BinaryNode(secondPoint.element);
parent.leftChild = secondPoint;
parent.rightChild = firstPoint;
firstPoint = secondPoint.next;
}
if (head == null) {
head = parent;
parentPoint = parent;
} else {
parentPoint.next = parent;
parentPoint = parent;
}
}
}
// 打印建二叉树的过程
BinaryNode y = head;
while (y != null) {
System.out.print(head.element + " ");
y = y.next;
}
System.out.println();
return head.element;
}
// 寻找次小值
public int secondSmall(int[] arr) {
if (arr.length < 2)
throw new RuntimeException("no second element");
int firstSmall = firstSmall(arr);
System.out.println("最小值为 : " + firstSmall);
int secondSmall = Integer.MAX_VALUE;
while (head.leftChild != null) {
if (head.rightChild == null) {
return secondSmall;
}
if (secondSmall > head.rightChild.element){
secondSmall = head.rightChild.element;
}
head = head.leftChild;
}
return secondSmall;
}
// 节点: 二叉树 + 链表
private class BinaryNode {
int element;
BinaryNode next;
BinaryNode leftChild;
BinaryNode rightChild;
public BinaryNode(int element) {
this.element = element;
next = null;
leftChild = null;
rightChild = null;
}
}
}
2.2 测试代码
package chapter9;
/**
* Created by wangbin on 2017/3/4.
* 测试代码
*/
public class Test9 {
public static void main(String[] args) {
int[] a = {1, 4, 7, 9, 8};
for (int i : a) {
System.out.print(i + " ");
}
System.out.println();
System.out.println("次小值为 : " + new Exercise911().secondSmall(a));
}
}