首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > JAVA > J2SE开发 >

java一道算法题,该怎么处理

2012-02-20 
java一道算法题有一个int数组,储存的数值范围在1至10000之间(不是10000以内的每一个数字都出现在数组中),

java一道算法题
有一个int数组,储存的数值范围在1至10000之间(不是10000以内的每一个数字都出现在数组中),数组本身没有排序,现在有一个数重复了,用最快的方法查出重复的数字。


[解决办法]
先分类 可以用二分法 直到发现相同的 即可 这样应该是最快的


[解决办法]
二分法 空间换时间

[解决办法]
二分法应该需要对已排序的数组操作吧 那如果排序的话 时间复杂度就超过了O(n)
[解决办法]
用一个boolean flag[10000] = {false};数组记录访问情况,例如 若 找到10,那么flag[10] = true;
遍历一遍,时间复杂度0(n);不知道会不会有比O(n) 更快的算法~希望大家继续加油思考,期待答案~
[解决办法]
a[10000]给定的数组,b[10000]新建的全为零的数组

for(int i = 0; i<10000; i++)
{
b[a[i]]++;
if(b[a[i]]==2) System.out.println(a[i]);
}
这样只需要遍历10000个数就好了 不知怎样做能更快些 希望楼主能得到更好的答案
[解决办法]

Java code
import java.util.Scanner;public class Main {    // 1至10000之间 数组最长就1000    // 打表就OK了,每读一个数字就以该数字为下标存入数字    // 如果给空间已经存储就说明这个数字重复了    // 最好O(2), 最坏O(n), 平均 O(n/2)    public static void main(String[] args) {        boolean[] a = new boolean[1001];        // 输入器        Scanner scanner = new Scanner(System.in);        int x;        // 如果输入器有数据        while (scanner.hasNext()) {            // 读取当前数据            x = scanner.nextInt();            // 如果是false,表示尚未使用该空间            // 则表示这个数没使用            if (!a[x]) {                // 就使用该空间                a[x] = true;            } else {                // 否则是true就说明已经出现了该数                System.out.println(x + "重复");                break;            }        }    }}// 1 2 3 4 5 6 7 8 9 10 1// 1重复 

热点排行