给两个已序数组，写一个函数求出第K小的数(听说是GOOGLE给出的题)给两个已序数组，写一个函数求出第K小的数(
给两个已序数组，写一个函数求出第K小的数(听说是GOOGLE给出的题)
给两个已序数组，写一个函数求出第K小的数(听说是GOOGLE给出的题)
根据上面题 目，随便写了一个JAVA版的实现。
package com.test;
public class Test {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int a1[] = { 5, 6, 7, 8, 48, 51, 55, 56, 182 };
int a2[] = { 4, 4, 5, 9, 41, 155, 522, 1566 };
Test.getNumber(1, a1, a2);
}
public static String getNumber(int index, int[] a1, int[] a2) {
LinkList list = null;
LinkList listTmp = null;
LinkList tmp = null;
int indexTmp = 0;
int length1 = a1.length, length2 = a2.length;
int p1 = 0, p2 = 0;
/*
* 验证输入index是否在合法的范围内
*/
if (length1 + length2 < index) {
System.out
.println("k超过了两个数据的长度!![如：a1长度为5，a2长度为12,index则取值为：1-17]");
return null;
}
/*
* 开始构造LinkList链表，将已排序的两个数组的数据封装到一个链表里边，并添加附加信息，如链表的索引index,相应数据在原来两个数组中的哪个里边local
*/
while (p1 < length1 && p2 < length2) {
if (null == list) {
list = new LinkList();
list.setLocal((byte) 0);
list.setIndex(indexTmp);
indexTmp++;
listTmp = list;
}
if (a1[p1] <= a2[p2]) {
tmp = new LinkList();
tmp.setLocal((byte) 1);
tmp.setValue(a1[p1]);
tmp.setListNode(null);
tmp.setIndex(indexTmp);
indexTmp++;
listTmp.setListNode(tmp);
listTmp = tmp;
p1++;
} else {
tmp = new LinkList();
tmp.setLocal((byte) 2);
tmp.setValue(a2[p2]);
tmp.setListNode(null);
tmp.setIndex(indexTmp);
indexTmp++;
listTmp.setListNode(tmp);
listTmp = tmp;
p2++;
}
}
/*
* 下面两个if只执行其中一个，视两个数据a1,a2的长度，以及数据来决定
*/
if (p1 < length1) {
for (; p1 < length1; p1++) {
tmp = new LinkList();
tmp.setLocal((byte) 1);
tmp.setValue(a1[p1]);
tmp.setListNode(null);
tmp.setIndex(indexTmp);
indexTmp++;
listTmp.setListNode(tmp);
listTmp = tmp;
}
}
if (p2 < length2) {
for (; p2 < length2; p2++) {
tmp = new LinkList();
tmp.setLocal((byte) 2);
tmp.setValue(a2[p2]);
tmp.setListNode(null);
tmp.setIndex(indexTmp);
indexTmp++;
listTmp.setListNode(tmp);
listTmp = tmp;
}
｝
/*
* 找到最小第K个数据，并返回
*/
while ((list.getListNode()) != null) {
if (list.getIndex() == index) {
String message = "第" + list.getIndex() + "个最小的数为"
+ list.getValue() + " 它在第" + list.getLocal()
+ "个数组里 ";
System.out.println(message);
return list.getValue() + "";
}
list = list.getListNode();
}
if (list.getIndex() == index) {
String message = "第" + list.getIndex() + "个最小的数为"
+ list.getValue() + " 它在第" + list.getLocal()
+ "个数组里 ";
System.out.println(message);
return list.getValue() + "";
}
return null;
}
}
class LinkList {
private int index;//链表，用于存放丙个数组里数据
private int value;
private byte local;// 0:表示链表头;1:数组1;2:数组2
private LinkList listNode;//指向下一个节点
public LinkList() {
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public byte getLocal() {
return local;
}
public void setLocal(byte local) {
this.local = local;
}
public LinkList getListNode() {
return listNode;
}
public void setListNode(LinkList listNode) {
this.listNode = listNode;
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
}
