上回看到一道微软的算法题，题目大概是说：有一个很大的整型数组，我们怎样能够找到一个不在这个数组中的值。
假设一个数组的大小很大（比如说35000个值），我们知道整型的取值范围在某种c/c++编译器中是16位的，也就只能到65536。那么怎样才能通过最少的代价找到不在这个数组中的整型值呢？！
解答：
1、我们可以利用像数数字一样的算法，来解答这个问题。比如说我们数1到10的时候，如果1到10都是连续的话，那么我们可以肯定在这个中间是不会存在不在这个范围类的值了，具体到这个环境中，我们同样可以这样考虑，假设我们把数组遍历一遍，把其中所有能够连续的数值都去掉，那么那些连续数值中间的不连续地段，就是我们要找的值的所在。
2、因为java语言对于数据结构的良好封装，这道题的java解答很简单也容易。首先我们描述下面一个数据结构：
/*
* Created on 2003-4-6
*
* To change this generated comment go to
* Window>Preferences>Java>Code Generation>Code and Comments
*/
package bia.arithmetic;
import java.io.PrintStream;
/**
* @author Administrator
*
* To change this generated comment go to
* Window>Preferences>Java>Code Generation>Code and Comments
*/
public class NumberNode {
int value ;
boolean hasLeft ;
boolean hasRight ;
NumberNode next,prev ;
public void print(PrintStream out){
String s = String.valueOf(value) ;
if (hasLeft){
s = "-" + s ;
}
else {
s = " " + s ;
}
if (hasRight){
s = s + "-" ;
}
else {
s = s + " " ;
}
out.print(s) ;
}
public NumberNode(){
value=0 ;
hasLeft = false ;
hasRight = false ;
}
/**
* @return boolean
*/
public boolean isHasLeft() {
return hasLeft;
}
/**
* @return boolean
*/
public boolean isHasRight() {
return hasRight;
}
/**
* @return NumberNode
*/
public NumberNode getNext() {
return next;
}
/**
* @return NumberNode
*/
public NumberNode getPrev() {
return prev;
}
/**
* @return int
*/
public int getValue() {
return value;
}
/**
* Sets the hasLeft.
* @param hasLeft The hasLeft to set
*/
public void setHasLeft(boolean hasLeft) {
this.hasLeft = hasLeft;
}
/**
* Sets the hasRight.
* @param hasRight The hasRight to set
*/
public void setHasRight(boolean hasRight) {
this.hasRight = hasRight;
}
/**
* Sets the next.
* @param next The next to set
*/
public void setNext(NumberNode next) {
this.next = next;
}
/**
* Sets the prev.
* @param prev The prev to set
*/
public void setPrev(NumberNode prev) {
this.prev = prev;
}
/**
* Sets the value.
* @param value The value to set
*/
public void setValue(int value) {
this.value = value;
}
}
然后，我们利用这个结构构造一个NumberList链表，来处理排序和依次读取的操作，在这个过程中，将中间连续的部分屏蔽掉，只留下连续的边界。
/*
* Created on 2003-4-6
*
* To change this generated comment go to
* Window>Preferences>Java>Code Generation>Code and Comments
*/
package bia.arithmetic;
import java.io.PrintStream;
/**
* @author Administrator
*
* To change this generated comment go to
* Window>Preferences>Java>Code Generation>Code and Comments
*/
public class NumberList {
NumberNode first;
public void print(PrintStream out){
out.println("======Begin print List======") ;
NumberNode p = first ;
while (null!=p){
p.print(out) ;
p = p.getNext() ;
}
out.println("\n======End print List======") ;
}
public NumberList() {
}
public NumberNode getFirst() {
return first;
}
public void addNumber(int number){
NumberNode node = new NumberNode() ;
node.setValue(number) ;
addNode(node) ;
}
/**
* 增加一个节点的方法
* @Renzhichao
* @param node
*/
public void addNode(NumberNode node) {
if (first == null) {
first = node;
first.setPrev(null);
first.setNext(null);
first.setHasLeft(false) ;
first.setHasRight(false) ;
}
else {
NumberNode tmp = first;
NumberNode p = tmp;
while (tmp.getValue() < node.getValue() && tmp.getNext() != null) {
p = tmp;
tmp = tmp.getNext();
}
if (tmp.getValue()<node.getValue()){
//node插在链表的结尾。
tmp.setNext(node) ;
node.setPrev(tmp) ;
node.setNext(null) ;
if (tmp.getValue()+1==node.getValue()){
tmp.setHasRight(true) ;
node.setHasLeft(true) ;
if (tmp.isHasLeft()&&tmp.isHasRight()){
p.setNext(node) ;
node.setPrev(p) ;
tmp=null ;
}
}
}
else if (tmp.getValue()>node.getValue()){
//node插在链表的中央。
if (tmp==first){
//首先判断tmp是不是first
first = node ;
first.setHasLeft(false) ;
first.setHasRight(false) ;
first.setNext(tmp) ;
first.setPrev(null) ;
tmp.setPrev(node) ;
if (first.getValue()+1==tmp.getValue()){
first.setHasRight(true) ;
tmp.setHasLeft(true) ;
if (tmp.isHasLeft()&&tmp.isHasRight()){
//去掉tmp节点
first.setNext(tmp.getNext()) ;
tmp = null ;
}
}
}
else {
if (p.getValue()+2 == tmp.getValue()){
//判断是不是p和tmp可以连续了
p.setHasRight(true) ;
tmp.setHasLeft(true) ;
}
else if (!p.isHasRight()&&!tmp.isHasLeft()){
p.setNext(node) ;
tmp.setPrev(node) ;
node.setPrev(p) ;
node.setNext(tmp) ;
if (p.getValue()+1 == node.getValue()){
p.setHasRight(true) ;
node.setHasLeft(true) ;
}
else if (node.getValue()+1==tmp.getValue()){
node.setHasRight(true) ;
tmp.setHasLeft(true) ;
}
}
}
}
}
}
}
|
本类阅读TOP10