一个人至少拥有一个梦想,有一个理由去坚强

心若没有栖息的地方,到哪里都是在流浪

java基础系列 06 | 如何有效地检查数组是否包含Java中的值?

如何检查数组(未排序)是否包含某个值?这是Java中非常有用且经常使用的操作。这也是Stack Overflow的最高投票问题。如最高投票答案所示,这可以通过几种不同的方式完成,但时间复杂度(time complexity )可能非常不同。本篇文章,将介绍每种方法的时间成本。

1、检查数组是否包含值的四种不同方法

1)使用List:

public static boolean useList(String[] arr, String targetValue) {
  return Arrays.asList(arr).contains(targetValue);
}

2)使用Set:

public static boolean useSet(String[] arr, String targetValue) {
  Set<String> set = new HashSet<String>(Arrays.asList(arr));
  return set.contains(targetValue);
}

3)使用简单的循环:

public static boolean useLoop(String[] arr, String targetValue) {
  for(String s: arr){
    if(s.equals(targetValue))
      return true;
  }
  return false;
}

4)使用Arrays.binarySearch():

binarySearch() 只能用于排序数组。如果数组已排序,您可以使用以下代码搜索目标元素:

public static boolean useArraysBinarySearch(String[] arr, String targetValue) {	
  int a =  Arrays.binarySearch(arr, targetValue);
  if(a > 0)
    return true;
  else
    return false;
}

 

3、时间复杂度(Time Complexity

可以使用以下代码测量大致的时间成本。基本思想是搜索大小为5,1k,10k的数组。这种方法可能不准确,但这个想法清晰而简单。

public static void main(String[] args) {
  String[] arr = new String[] {  "CD",  "BC", "EF", "DE", "AB"};
 
  //use list
  long startTime = System.nanoTime();
  for (int i = 0; i < 100000; i++) {
    useList(arr, "A");
  }
  long endTime = System.nanoTime();
  long duration = endTime - startTime;
  System.out.println("useList:  " + duration / 1000000);
 
  //use set
  startTime = System.nanoTime();
  for (int i = 0; i < 100000; i++) {
    useSet(arr, "A");
  }
  endTime = System.nanoTime();
  duration = endTime - startTime;
  System.out.println("useSet:  " + duration / 1000000);
 
  //use loop
  startTime = System.nanoTime();
  for (int i = 0; i < 100000; i++) {
    useLoop(arr, "A");
  }
  endTime = System.nanoTime();
  duration = endTime - startTime;
  System.out.println("useLoop:  " + duration / 1000000);
}

结果:

useList:  13
useSet:  72
useLoop:  5

 

使用1000大小的数组:

String[] arr = new String[1000];
 
Random s = new Random();
for(int i=0; i< 1000; i++){
  arr[i] = String.valueOf(s.nextInt());
}

结果:

useList:  112
useSet:  2055
useLoop:  99
useArrayBinary:  12

 

使用100000大小的数组:

String[] arr = new String[10000];
 
Random s = new Random();
for(int i=0; i< 10000; i++){
  arr[i] = String.valueOf(s.nextInt());
}

结果:

useList:  1590
useSet:  23819
useLoop:  1526
useArrayBinary:  12

显然,使用简单的循环方法比使用任何集合更有效。很多开发人员使用第一种方法,但效率很低。将数组推送到另一个集合需要旋转所有元素以读取它们,然后再对集合类型执行任何操作。

如果使用 Arrays.binarySearch() 方法,则必须对数组进行排序。在这种情况下,数组未排序,因此不应使用它。实际上,如果需要检查某个数组/集合中是否有效地包含某个值,则排序列表或树时间复杂度为O(log(n),或者hashset时间复杂度为O(1)。

 

更多精彩,请扫码关注博主个人公众号

《java基础系列 06 | 如何有效地检查数组是否包含Java中的值?》

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注