A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

本帖最后由 Chelsea_Lampard 于 2013-5-10 21:46 编辑

有一个数组放有很多数据,比如1到1000的数字,并且不是有序的 现在要快速从其中查找一个数字存不存在  我们往常写就是for循环一个一个去比较  这显然效率是低的 有没有更好的算法来提高效率。求大虾啊 啊啊啊 啊啊。能附上代码就好了!!拜谢各位。

评分

参与人数 1技术分 +1 收起 理由
Sword + 1

查看全部评分

13 个回复

倒序浏览
还不是有序的,这个好高难度,如果允许使用数组工具什么的倒很容易弄。
( java.util.Arrays类) Arrays.sort( 指定需要排序的数组名 ) ;    这个数组工具可以对数组进行排序,之后就可以用二分查找或者其他的方法去寻找是否存在。
如果要获取这个数组中指定数字的角标位置的话,那么就应该要用到集合那些类来实现了。
回复 使用道具 举报
有用hash算法。。。hash算法的目的就是提高查询。。。。
回复 使用道具 举报
个人理解,先排序,再二分查找下
回复 使用道具 举报
这是我做的两种查找的方式你参考一下:
//数组的查找操作
class ArraySearch
{
       
        //一般的查找方式
        public static int getIndex(int[] arr,int key)
        {
                for(int x=0;x<arr.length;x++)
                {
                        if(arr[x]==key)
                          return x;
                }
                return -1;
        }
       
        /*
          这折半查找:要求对有序的数组进行操作
         */
         public static int halfSearch(int[] arr,int key)
         {
                 int min,max,mid;
                 min=0;
                 max=arr.length-1;
                 mid=(min+max)/2;
                 while(arr[mid]!=key)
                 {
                         if(key>arr[mid])
                                 min=mid+1;
                         else if(key<arr[mid])
                                 max=mid-1;
                                 if(min>max)
                         return -1;
                         mid=(min+max)/2;
                 }
                 return mid;
         }
         /*
         折半查找的另一种方式
         */
         public static int halfSearch2(int[] arr,int key)
         {
                 int min,max,mid;
                 min=0;
                 max=arr.length-1;
                 while(min<=max)
                 {
                         mid=(min+max)/2;
                         if(key>arr[mid])
                                 min=mid+1;
                         else if(key<arr[mid])
                                 max=mid-1;
                                 else
                          return mid;
                 }
         return -1;
         }
         
         
    public static void main(String args[])
    {
            int[] arr={1,4,6,7,8};
            //int index=getIndex(arr,6);
            //System.out.println("index="+index);
        // int index2=halfSearch(arr,7);
            //System.out.println("index2="+index2);
           
            int index3=halfSearch2(arr,7);
            System.out.println("index3="+index3);
    }
}

评分

参与人数 1技术分 +1 收起 理由
Sword + 1

查看全部评分

回复 使用道具 举报
本帖最后由 杨兴庭 于 2013-5-9 18:01 编辑

楼主所说的快速查找方法数组应该做不了,,楼主所说要快速从其中查找一个数字在数组中存不存在,提高查找效率,集合可以实现,将你要查找的数看做一个个对象,将对象存储到集合里,用HashMap()中的containsKey()方法可以快速判定要查找的数的键是否在集合中存在。
例如:根据书本编号,快速确定书库中是否存在这本书
理解思路:根据判断用户所输入的“键”,在键集合中是否存在,就能快速判断出书库中有没有这本书。题目中的书就可以理解楼主所说要找的数,书库相当于楼主所说的数组。具体代码如下:

public class Book {

/*声明对象*/
private String name;

    /*getter、setter方法*/
public String getName() {
  return name;
}
public void setName(String name) {
  this.name = name;
}
  
/*构造方法*/
public Book(String name) {
  super();
  this.name = name;
}

/*String toString方法*/
@Override
public String toString() {
  return name;
}
}



import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;
public class TestBook {
/**
  * HashMap用法
  */
public static void main(String[] args) {
  
       /*声明对象*/
  Book c=new Book("c语言");
  Book sql=new Book("SQl数据库");
  Book java=new Book("java程序设计");
  
  /*声明集合*/
  Map a=new HashMap();
  
  /*向集合中加入数据*/
  a.put("001", c);
  a.put("002", sql);
  a.put("003",java);

System.out.print("请输入图书编号:");
  Scanner input=new Scanner(System.in);
  
  String id=input.next();
  
  /*判断集合中是否有书本编号是001的书*/

  if(a.containsKey(id)){
   System.out.println(a.get(id));
  }
  else{
   System.out.println("对不起,没有这本书");
  }
  
}
}

评分

参与人数 1技术分 +1 收起 理由
Sword + 1 请注意,以后点击&quot;&lt;&gt;&quot;插入代码.

查看全部评分

回复 使用道具 举报
小石头39910 发表于 2013-5-9 16:52
这是我做的两种查找的方式你参考一下:
//数组的查找操作
class ArraySearch

看你的头像,甚觉似曾相识.
改变下思维.这种方式也行,不过效率肯定不高...
  1. public static void main(String[] args) {
  2.                 System.out.println(Arrays.toString(getArray(1000,100)).indexOf(""+15));
  3.         }
  4.         /**
  5.          * n是数组的长度,max生成最大可能数
  6.          */
  7.         public static int[] getArray(int n,int max){
  8.                 int[] arr=new int[n];
  9.                 Random rand=new Random();
  10.                 for(int i=0;i<n;i++){
  11.                         arr[i]=rand.nextInt(max)+1;
  12.                 }
  13.                 System.out.println("原始数组:"+Arrays.toString(arr));
  14.                 return arr;
  15.         }
复制代码

评分

参与人数 1技术分 +1 收起 理由
Sword + 1 回答的简洁明了,顶一个

查看全部评分

回复 使用道具 举报
先来个冒泡排序 再来个折半查找啊。
回复 使用道具 举报
你好   ,这个可以通过折半查找的方式来解决  。。因为折半查找效率高出普通查找很多   
public static int find(int[] arr , int key) {
                int min = 0 ;                        //最小角标位
                int max = arr.length-1;        //最大角标位
                int mid = (min + max)/2;//中间角标位初始化
                while (arr[mid] != key){        //只要数字不等于key,就一直循环
                        if (key > arr[mid]){        //要是key大于中间角标位。
                                min = mid + 1 ;                //min就到mid的右边去
                        }else if (key < arr [mid]){//要是key小于中间角标位
                                max = mid -1;                        //max就到mid的左边去
                        } if(min > max) {                        //假如最小角标到最大角标右边去了,那么直接输入-1.
                                return -1;                                //输出-1说明找不到
                        }
                        mid = (min+max) / 2 ;                //将中间角标折半
                }
                return mid ;                                        //返回找到的数。
        }


这是折半查找的代码   我学的时候写的   要是有看不懂的地方再回复我

评分

参与人数 1技术分 +1 收起 理由
Sword + 1

查看全部评分

回复 使用道具 举报
本帖最后由 刘学明    于 2013-5-9 23:54 编辑
陈圳 发表于 2013-5-9 18:27
看你的头像,甚觉似曾相识.
改变下思维.这种方式也行,不过效率肯定不高... ...


怎么看着一点也没沾边啊  {:2_33:}
回复 使用道具 举报
用set集合做。。。最方便的就是着一个了。。什么排序的都弱爆了。
我帮你手动写一个吧;
public static void main(String[] args)
{
boolean[]  flag =  new boolean[1002];//根据你的意思是1-1000
Scanner cin = new Scanner(System.in);
int n,m;//m 为你要输入的 数组的大小
m = cin.nextInt();
while(m--)
{
// 输入n n为要输入的数据
n = cin.nextInt();
flag[n]=true;
}
m = cin.nextInt();// 输入你要查询数据的的个数
while(m--)
{
n = cin.nextInt();// n 你要查询的数据
if(!flag[n]) System.out.println("你要查询的数据"+n+"不存在");
else  System.out.println("恭喜 查询成功");
}
}

基本就是这么干的。。
其实当数据很大的时候 比如 查询的数据有 1-10^10  而且 数组中存放的数据不超过 10w 就要考虑使用hash了,,
hash的出现就是为了提高查询速度。。
如果问题以解决,请及时修改分类谢谢合作

评分

参与人数 1技术分 +1 收起 理由
Sword + 1

查看全部评分

回复 使用道具 举报
如果单从数组存储的角度来考虑,并且是无序的话,没有好的方法来查找一个数。无序存储很多数并且还需要查找功能的话,一般是不用数组存储的,建议用其它的存储结构。
回复 使用道具 举报
可以用折半查找算法。
回复 使用道具 举报
zms2100 发表于 2013-5-9 11:02
还不是有序的,这个好高难度,如果允许使用数组工具什么的倒很容易弄。
( java.util.Arrays类) Arrays.sort ...

楼上正解,我当时做这道题就是用的这种,思路给楼主就是了,代码建议还是楼主自己写吧。。。
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马