在O（1）中查找数组值大于x的第一个索引

2 回答

• 1

  为了能够通过数组找到具有特定属性（例如：大于目标）的值的索引，您必须遍历实现搜索算法的数组 .

  Therefore O(1) is not possible to achieve.

  • 如果数组已经排序，正如您在示例中所示，您可以通过实现二进制搜索算法在O（log（n））中实现所需 . 您也可以使用java.util.Arrays中的实现 .

  • 如果数组未排序，则必须使用具有O（n）复杂度的线性搜索算法在最坏的情况下遍历数组的所有元素 .

  回复于 2024-04-26T18:41:09+08:00
• 5

  如果你准备一个这样的索引数组（或map） .

  int[] a = {1,4,7,9,15,30};
      // prepare indices array
      int[] indices = new int[a[a.length - 1] + 1];
      for (int i = 0, j = 0, aLength = a.length; i < aLength; ++i)
          while (j <= a[i])
              indices[j++] = i;
      System.out.println(Arrays.toString(indices));
      // -> [0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5]
      // get the first index whose value is greater than a target in O(1)
      System.out.println(indices[10]); // -> 4 (index of 15)
  

  您可以在O（1）中通过 indices[target] 获取索引值 .

  回复于 2024-04-26T18:41:09+08:00