问题

怎样去判断Array(无序)中是否包含某个值呢?

这是一个在Java中经常被问到的问题。它也是Stack Overflow上投票前几的一个问题。下面将展示投票前几的几个回答,这些回答使用不同的方式解决了这个问题,但是,时间复杂度也是各有不同的。

四种解决方法

使用List

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

使用Set

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

使用Loop

  1. public static boolean useLoop(String[] arr, String targetValue) {
  2. for (String s : arr) {
  3. if (s.equals(targetValue))
  4. return true;
  5. }
  6. return false;
  7. }

使用ArraysBinarySearch,这个方法只适用于已排序的Array

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

时间复杂度

这大概的运行时间可以通过下面的代码进行衡量。这基本的思路是通过在大小分别为5,1k,10k的Array中进行查找。这个方法可能不够精确,但是这个思路还是很简单清晰的。

使用Array大小为5

  1. public static void main(String[] args) {
  2. System.out.println("---------array size is 5-----------");
  3. String[] arr = new String[] { "CD", "BC", "EF", "DE", "AB" };
  4. //use list
  5. long startTime = System.nanoTime();
  6. for (int i = 0; i < 100000; i++) {
  7. useList(arr, "A");
  8. }
  9. long endTime = System.nanoTime();
  10. long duration = endTime - startTime;
  11. System.out.println("useList: " + duration / 1000000+" 毫秒");
  12. //use set
  13. startTime = System.nanoTime();
  14. for (int i = 0; i < 100000; i++) {
  15. useSet(arr, "A");
  16. }
  17. endTime = System.nanoTime();
  18. duration = endTime - startTime;
  19. System.out.println("useSet: " + duration / 1000000+" 毫秒");
  20. //use loop
  21. startTime = System.nanoTime();
  22. for (int i = 0; i < 100000; i++) {
  23. useLoop(arr, "A");
  24. }
  25. endTime = System.nanoTime();
  26. duration = endTime - startTime;
  27. System.out.println("useLoop: " + duration / 1000000+" 毫秒");
  28. //use Arrays.binarySearch()
  29. startTime = System.nanoTime();
  30. for (int i = 0; i < 100000; i++) {
  31. useArraysBinarySearch(arr, "A");
  32. }
  33. endTime = System.nanoTime();
  34. duration = endTime - startTime;
  35. System.out.println("useArrayBinary: " + duration / 1000000+" 毫秒");
  36. }

结果:

  1. ---------array size is 5-----------
  2. useList: 10 毫秒
  3. useSet: 66 毫秒
  4. useLoop: 4 毫秒
  5. useArrayBinary: 4 毫秒

### 使用Array大小为1k

  1. System.out.println("---------array size is 1k----------");
  2. String[] arr = new String[1000];
  3. Random s = new Random();
  4. for (int i = 0; i < 1000; i++) {
  5. arr[i] = String.valueOf(s.nextInt());
  6. }

结果:

  1. ---------array size is 1k----------
  2. useList: 762 毫秒
  3. useSet: 7549 毫秒
  4. useLoop: 677 毫秒
  5. useArrayBinary: 14 毫秒

使用Array大小为10k

  1. System.out.println("---------array size is 10k---------");
  2. String[] arr = new String[10000];
  3. Random s = new Random();
  4. for (int i = 0; i < 10000; i++) {
  5. arr[i] = String.valueOf(s.nextInt());
  6. }

结果:

  1. ---------array size is 10k---------
  2. useList: 7395 毫秒
  3. useSet: 126341 毫秒
  4. useLoop: 5776 毫秒
  5. useArrayBinary: 17 毫秒

总结

从测试的结果可以清楚地知道,使用简单的Loop比使用集合操作更加有效 。许多开发者使用List方式,但是那并不高效。把Array放到另一个Collection中需要读取Array中的所有元素,这将花费不少的时间。

使用Arrays.binarySearch()的前提是这Array必须是有序的。

实际上,如果你真正需要高效地去判断Array/Collection中是否包含某个值,一个排序了的List或者Tree的时间复杂度为O(log(n)),或者用HashSet,它的时间复杂度为O(1)。

原文链接:http://www.programcreek.com/2014/04/check-if-array-contains-a-value-java/

翻译:crane-yuan

[ 转载请保留原文出处、译者和译文链接。]

05-11 11:23