黑马程序员技术交流社区

标题: 怎么很快的从数组中判断一个数据存不存在 [打印本页]

---

作者: Chelsea_Lampard    时间: 2013-5-9 10:35
标题: 怎么很快的从数组中判断一个数据存不存在


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

---

作者: zms2100    时间: 2013-5-9 11:02
还不是有序的，这个好高难度，如果允许使用数组工具什么的倒很容易弄。
( java.util.Arrays类) Arrays.sort( 指定需要排序的数组名 ) ;    这个数组工具可以对数组进行排序，之后就可以用二分查找或者其他的方法去寻找是否存在。
如果要获取这个数组中指定数字的角标位置的话，那么就应该要用到集合那些类来实现了。

---

作者: 刘胜寒    时间: 2013-5-9 11:55
有用hash算法。。。hash算法的目的就是提高查询。。。。

---

作者: 金辉    时间: 2013-5-9 16:40
个人理解，先排序，再二分查找下

---

作者: 小石头39910    时间: 2013-5-9 16:52
这是我做的两种查找的方式你参考一下：
//数组的查找操作
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);
    }
}

---

作者: 杨兴庭    时间: 2013-5-9 18:00


楼主所说的快速查找方法数组应该做不了，，楼主所说要快速从其中查找一个数字在数组中存不存在，提高查找效率，集合可以实现，将你要查找的数看做一个个对象，将对象存储到集合里，用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("对不起，没有这本书");
  }
  
}
}

---

作者: 陈圳    时间: 2013-5-9 18:27

小石头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.         }

复制代码

---

作者: 王靖远    时间: 2013-5-9 18:52
先来个冒泡排序 再来个折半查找啊。

---

作者: 黑马-雷钊    时间: 2013-5-9 19:44
你好   ，这个可以通过折半查找的方式来解决  。。因为折半查找效率高出普通查找很多   
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 ;                                        //返回找到的数。
        }


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

---

作者: 刘学明　　　    时间: 2013-5-9 23:53

陈圳 发表于 2013-5-9 18:27
看你的头像,甚觉似曾相识.
改变下思维.这种方式也行,不过效率肯定不高... ...

怎么看着一点也没沾边啊  {:2_33:}

---

作者: 刘胜寒    时间: 2013-5-10 12:51
用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的出现就是为了提高查询速度。。如果问题以解决，请及时修改分类谢谢合作

---

作者: 石贤芝    时间: 2013-5-10 20:50
如果单从数组存储的角度来考虑，并且是无序的话，没有好的方法来查找一个数。无序存储很多数并且还需要查找功能的话，一般是不用数组存储的，建议用其它的存储结构。

---

作者: Leejuen    时间: 2013-5-10 21:03
可以用折半查找算法。

---

作者: Miss小强    时间: 2013-5-10 21:14

zms2100 发表于 2013-5-9 11:02
还不是有序的，这个好高难度，如果允许使用数组工具什么的倒很容易弄。
( java.util.Arrays类) Arrays.sort ...

楼上正解，我当时做这道题就是用的这种，思路给楼主就是了，代码建议还是楼主自己写吧。。。

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2