随机数构成的数组中找到长度大于=3的最长的等差数列
来自：http://www.iteye.com/problems/64504?page=2
@SuppressWarnings("unchecked") private static void getArithmeticProgression(int[] array) { /* 排序 */ Arrays.sort(array); /* 存放最大等差数列的容器 */ ArrayList<Integer> maxList = new ArrayList<Integer>(); /* 存放等差数列的临时容器 */ ArrayList<Integer> tmpList = new ArrayList<Integer>(); int len = array.length; for (int i = 0; i < len; i++) { for (int j = i + 1; j < len; j++) { /* 清空list */ tmpList.clear(); /* 添加数列的第一个元素 */ tmpList.add(i); /* 添加数列的第二个元素*/ tmpList.add(j); /* 当前数列的元素个数 */ int num = 2; /* 等差 */ int progression = array[j] - array[i]; /* 当前元素位置 */ int current = j; /* 下一个元素位置 */ int next = j + 1; /* 从current开始遍历*/ while (next < len) { /*下一个元素和当前元素是等差数列*/ if (array[next] - array[current] == progression) { tmpList.add(next); current = next; num++; } next++; } /* 设定最大等差数列*/ if (num >= maxList.size()) { maxList = (ArrayList<Integer>)tmpList.clone(); } } } /* 输出结果 */ for (Integer o : maxList) { System.out.println(array[o]); } } 1 楼 chriszeng87 2011-08-30 这个效率也太低了吧 2 楼 hudingchen 2011-09-02 chriszeng87 写道这个效率也太低了吧