给定排序整数数组，根据A [i] = i的除法和征服写一个算法

3 回答

• 2

  输入本身排序的要求是不够的 . 输入数组中没有两个相等值的附加要求是能够使用二进制搜索的必要条件 .

  如果这不是条件，则无法使用二进制搜索，如以下示例所示（假设0是第一个索引）：

  i:   0 1 2 3 4 5 6
          --------------
    A[i]: -1 0 x 4 y 6 7
                 ^
  

  使用二进制搜索，您将获取中间元素并决定它的哪一侧可能有 i 与 A[i]=i . 问题在于，在上面的示例中，解决方案可能位于中心的任一侧：如果 x=2 ，则解决方案位于左侧，而当 y=4 时，解决方案位于右侧 . 因此分而治之无效 . 只有当确保输入没有重复值时，才能使用分而治之算法 .

  最重要的是，您可以立即排除第一个值大于0的输入数组，因为如果没有重复值，就无法实现 A[i]=i . 类似地，最后一个值小于最后一个索引的输入数组没有 i 和 A[i]=i .

  这种考虑也将在分而治之的过程中发挥作用 . 举个例子：

  i:   0 1 2 3 4 5 6 7 8
          -------------------
    A[i]: -4 0 1 2 5 6 7 8 10
  

  首先验证两端的两个值：它们不排除解决方案，因此采用索引4处的中间值 . 由于其值（5）大于索引（4），因此可以忽略从索引4到8的范围 . 因此，在算法的下一次迭代中，考虑索引0和3（包括）之间的范围 .

  但是最右边的索引（3）的值小于3（它是2） . 通过上面提到的规则，这意味着没有解决方案，因此算法可以在那里停止：进行更多的划分将是徒劳的 .

  所以这是一个JavaScript实现：

  function hasSelfReference(arr) {
      let last = arr.length - 1;
      if (last < 0 || arr[0] > 0 || arr[last] < last) return false;
  
      let first = 0;
      while (first < last) {
          let mid = (first + last) >> 1;
          if (arr[mid] < mid) {
              first = mid + 1;
              if (arr[first] > first) return false;
          } else if (arr[mid] > mid) {
              last = mid - 1;
              if (arr[last] < last) return false;
          } else 
              return true;
      }
      return arr[first] === first; // arr[first] may be undefined: not a problem in JS
  }
  
  console.log(hasSelfReference([3, 4, 5, 6])); // false
  console.log(hasSelfReference([-4, -2, 1, 2, 7])); // false
  console.log(hasSelfReference([-4, -2, 1, 3, 7])); // true
  console.log(hasSelfReference([])); // false
  console.log(hasSelfReference([-4, 0, 1, 2, 5, 6, 7, 8, 10])); // false
  

  与通常的分而治之算法一样，这具有O（logn）（最坏情况）时间复杂度 .

  当数组具有匹配的索引时，则迭代次数为logn，但是当没有匹配且数组很大时，通常会提前退出循环 .

  回复于 2024-04-19T09:22:04+08:00
• 2

  让我们看一个例子：假设A [i] = i-1表示所有索引都是k，其中A [k] = k . 只是在一个地方对阵列进行采样并不会告诉你关于k的位置的任何信息（除非你碰巧用纯粹的运气击中了k） .

  因此，我不认为你可以比O（n）更好地获得最坏情况的运行时 .

  回复于 2024-04-19T09:22:04+08:00
• 1

  我认为最好使用二进制搜索

  1）您将获得有序整数

  2）你需要一个分而治之的算法

  3）二分搜索的运行时间为O（logn），优于线性搜索

  回复于 2024-04-19T09:22:04+08:00