请各位大虾帮忙看看这个问题该如何解决？

Question

检测一个集合中的元素是否是有序数字，并且最大的数字必须为这个集合的长度即(size) 请问该如何实现（高效的算法）~！
如：List list = new ArrayList();
    list.add("1");
    list.add("2");
    list.add("3");
    list.add("4");
    list.add("5");
这样是合法的，如出现 1,3,4,5,6 、1,2,2,3,4 

Answer 1

一次遍历：    public static boolean isLegal(List<Integer> list) {
        boolean ret = true;
        int last = -Integer.MAX_VALUE;
        if (list.get(list.size() - 1) <= list.size()) {
            for (int i = 0; i < list.size(); i++) {
                if (list.get(i) < last) {
                    ret = false;
                    break;
                }
                last = list.get(i);
            }
        } else {
            ret = false;
        }
        return ret;
    }

Answer 2

public boolean validata(List<Integer> list){
Integer last = Integer.MAX_VALUE;
int size = list.size();
//如果最后一个不等于list的长度则直接返回false
if(size != list.get(size)){
return false;
}
for(int i = size - 1; i >= 0; i--){
int value = list.get(i);
//如果后面一个比前面一个小，则直接返回false
if(last < value){
return false;
}
last = value;
}
return true;
}

Answer 3

public class ArraySetDemo { public static void main(String[] args) {
List<Integer> list = new ArrayList<Integer>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
System.out.println(check(list)); //true
list.remove(2); //1 3 4 5
System.out.println(check(list)); //false
list.add(1); //1 1 3 4 5
System.out.println(check(list)); //false
} private static boolean check(List<Integer> list) {
if (Collections.min(list)!=1) return false;
if (Collections.max(list)!=list.size()) return false;
Set<Integer> set = new HashSet<Integer>();
for(Integer i: list) set.add(i);
if (set.size()<list.size()) return false;
return true;
}}

Answer 4

代码很干净,很简洁,还有一些细节可以改进,比如 ret的初始值设为false(这也是通常做法），这样后面可以省略几次赋值语句。-Integer.MAX_VALUE？？

Answer 5

一个方法里面有很多return不容易维护，个人不喜欢。

Answer 6

4楼可能在考虑性能优化，这样可以达到吗？
这个问题，如果List基数很大，几百亿，几千亿，可以考虑增加步长来提高效率。

Answer 7

修改一下1L    
    public static boolean isLegal(List<Integer> list) {
        boolean ret = (list.get(list.size() - 1) == list.size());
        if (ret) { //先判断最后位是否和size一样
            for (int i = list.size()-1; i > 0; i--) {
                if (list.get(i) <= list.get(i-1)) { //再判断相邻两位是否有序
                    ret = false; //如果后一个位置的元素<=前一个位置的元素，则非有序
                }
            }
        }
        return ret;
    }

Answer 8

Set sequences = new  TreeSet();
for (int i=0;i<10;i++) {
sequences.add(i);
}
sequences.add(11);
Integer max = (Integer) ((TreeSet) sequences).last();
System.out.println("最大值："+max+","+sequences.size());
if(max != sequences.size()){
System.out.println("不符合规则，请确认");
}
我自己写了一个~，请各位看看 是否可行！

Answer 9

public class ArraySetDemo {    public static void main(String[] args) {
        List<Integer> list = new ArrayList<Integer>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        System.out.println(check(list)); //true
        list.remove(2); //1 3 4 5
        System.out.println(check(list)); //false
        list.add(1); //1 1 3 4 5
        System.out.println(check(list)); //false
    }    private static boolean check(List<Integer> list) {
        if (Collections.min(list)!=1) return false;
        if (Collections.max(list)!=list.size()) return false;
        Set<Integer> set = new HashSet<Integer>();
        for(Integer i: list) set.add(i);
        if (set.size()<list.size()) return false;
        return true;
    }}

Answer 10

如题，1,3,4,5,6 、1,2,2,3,4是不合法的，因为6和4均不是集合长度
应该是1，2，3，3，5或1，3，3，3，4，6下面用迭代器遍历一遍即可import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;public class Test02 { public static void main(String[] args) {
List<Integer> list = new ArrayList<Integer>();
list.add(1);
list.add(2);
list.add(3);
list.add(3);
list.add(5);
System.out.println(checkList(list));
} static boolean checkList(List<Integer> list){
Iterator<Integer> iterator = list.iterator();
int min = Integer.MIN_VALUE;
int num = -1;
while(iterator.hasNext()){
num = iterator.next();
if(num < min)
return false;
min = num;
}
return num == list.size();
}
}

Answer 11

不错。TreeSet本身可以排除重复元素，同时又可以排序，用得比较巧妙。