一个公司的Java面试题

9494.
像这种试题，你写循环都是不理想的答案。
逆向思维考虑吧！能用正常循环判断解决的，没必要拿出来考你了。

我用一次循环解决我觉得已经是最少的了...
这....不用循环如何解决,实在想不出来.求教

1、先把数组里的数字 都放到Set里面
   目的:去重复
2、把set转换成list，然后排序
   目的：去重复后的数字排序
3、取list中的第一个值a和最后一个值b,然后判断 b-a+1 = list.size()
   目的：返回true，说明连续
         返回false，说明不连续

.................说错了 

为什么不能用正常循环判断?

	public static void main(String[] args) {
		int[] arr = {1,5,2,4,3};
		Map<Integer,Integer> map = new TreeMap<Integer, Integer>();
		for(int i : arr){
			map.put(i, (i-1));
		}
		boolean firstIsNull =true;
		for(int i : map.keySet()){
			if(map.get(map.get(i))!=null){
				continue;
			}else if(firstIsNull){
				firstIsNull = false;
			}else{
				System.out.println("broken link" + i);
				break;
			}
		}
		
	}

public class StarEnds  {
	LinkedList<StarEnd> qeuqeu = new LinkedList<StarEnd>();
	public StarEnds add(StarEnd other) {
		Iterator<StarEnd> it = qeuqeu.iterator();
		while(it.hasNext()){
			StarEnd temp = it.next();
			if(StarEnd.isMix(temp, other)){
				other.inputOther(temp);
				it.remove();
			}
		}
		qeuqeu.add(other);
		return this;
	}	
	public Iterator<StarEnd> iterator(){
		return qeuqeu.iterator();
	}
	 

	public static void main(String[] args) {
		StarEnds ses = new StarEnds();
		int[] arr = {1,2,4,5};
		for(int i : arr){
			StarEnd temp = new StarEnd();
			temp.star=i;
			temp.end =i+1;
			ses.add(temp);
		}
		System.out.println(ses.qeuqeu);
	}


}
 class StarEnd{
	int star=0; 
	int end=0;
	@Override
	public String toString() {
		return "{"+star+":"+end+"}";
	}
	public void inputOther(StarEnd other){
		    List<Integer> l = Arrays.asList(star,end,other.star,other.end);
			star =  Collections.min(l);
			end =   Collections.max(l);
			other.star = 0;
			other.end = 0;
	
	}
	public static boolean isMix(StarEnd one, StarEnd other) {
		if(one==null||other==null){
			return false;
		}
		return one.inStarEnd(other.star)||one.inStarEnd(other.end) ;
	}
	public boolean inStarEnd(int in){
		return (in >= star && in<= end);
	}
}

先排个序，然后用map存，好像会好一点，有重复的就不添加，最后再看map中少不少...

  public static void main(String[] args) {
        // TODO Auto-generated method stub

        int[] intArr = { 1, 1, 3, 4, 5, 6 };
        Arrays.sort(intArr);
        List alist = new ArrayList();
        for (int i = 0; i < intArr.length; i++) {
            alist.add(intArr[i]);
        }
        HashSet hs = new HashSet();
        hs.addAll(alist);
        alist.clear();
        Iterator it = hs.iterator();
        while (it.hasNext()) {
            alist.add(it.next());
        }
        int max = (Integer) alist.get(alist.size() - 1);
        int min = (Integer) alist.get(0);
        if ((max - min) == alist.size() - 1) {
            System.out.println("是连续的");
        } else {
            System.out.println("不是连续的");
        }

    }

只要去掉重复的的数字后的数组长度!=最大值-最小值,返回false

	public static boolean isContinousArray(int[] intArr){
		char[] tempArr = new char[10];
		Arrays.fill(tempArr, ' ');
		for (int i:intArr) {
			tempArr[i] = '1';
		}
		String tempStr =new String(tempArr);
		if (tempStr.trim().contains(" ")) {
			return false;
		} else {
			return true;
		}
	}

如果里面数字只有0-9，那么这样是最快的。

一般来说，考一个简单的算法，前提都是
只能用基本数据类型和数组，然后再考虑最优的时间和空间复杂度。


如果题目复杂，可以用现有的各种基础数据类型，链表，堆，hash等，但是这些东西运行时其本身的时间和空间复杂度必须要计算在内。

本题用
set map sort
都是末流。

基于数组的三次循环，感觉已经是目前能想到的最优的了。
重复数据的问题，可以简单修正。