给定未排序的整数数组，查找不可搜索的数字

Question

朋友的面试问题

给定一个未排序的整数数组，使用二进制搜索无法找到多少个数字？

例如，[2, 3, 4, 1, 5]，只有数字1不能使用二分查找，因此Count=1

[4,2,1,3,5]4以及4和2不可搜索=

预期运行时间为O（n）

想不出能实现O（n）时间的算法：（

然而，考虑构建最小和最大arr时，子阵列可能会再次出错，因此无法工作。

显然，我们已经知道O（nlogn）方法，只需对每个数字调用二进制搜索并进行检查。

Answer 1

想法：这个问题可以改写为——找出数组中大于左边所有数字、小于右边所有数字的数字的计数。进一步简化后，找出左侧大于最大数且右侧小于最小数的数的计数。

代码：Java 11 |时间/空间：O（n）/O（n）

int binarySearchable(int[] nums) {
    var n = nums.length;
   
    var maxToLeft = new int[n + 1];
    maxToLeft[0] = Integer.MIN_VALUE;
   
    var minToRight = new int[n + 1];
    minToRight[n] = Integer.MAX_VALUE;
   
    for (var i = 1; i < n + 1; i++) {
        maxToLeft[i] = Math.max(maxToLeft[i - 1], nums[i - 1]);
        minToRight[n - i] = Math.min(minToRight[n  + 1 - i], nums[n - i]);
    }

    for (var i = 0; i < n; i++)
        if (nums[i] >= maxToLeft[i + 1] && nums[i] <= minToRight[i + 1])
            count++;
    return count;
}

• TopCoder问题：https://community.topcoder.com/stat?c=problem_statement

Answer 2

尝试创建以下函数：

def count_unsearchable(some_list, min_index=None, max_index=None, min_value=None, max_value=None):
    """How many elements of some_list are not searchable in the
       range from min_index to max_index, assuming that by the time
       we arrive our values are known to be in the range from
       min_value to max_value.  In all cases None means unbounded."""
    pass #implementation TBD

可以通过在时间O（n）中运行的方式实现此功能。它比朴素方法更快的原因是，在每个范围内只进行一次递归调用，而不是在该范围内的每个元素进行一次递归调用。

Answer 3

我相信这个代码工作正常。它对列表中的每个值进行一次遍历，所以它是O（n）。

function CountUnsearchable(list, minValue = -Infinity, maxValue=Infinity) {
  if (list is empty) return 0;
  let midPoint = mid point of "list"
  let lowerCount = CountUnsearchable(left half of list, minValue, min(midPoint, maxValue));
  let upperCount = CountUnsearchable(right half of list, max(minValue, midPoint), maxValue);
  let midPointUnsearchable = 1 if midPoint less than minValue or greater than maxValue, otherwise 0;
  return lowerCount + upperCount + midPointUnsearchable;
}

它是有效的，因为我们在树上行走有点像在二元搜索中，除了在每个节点上我们都走这两条路径，并简单地跟踪可能导致我们走这条路径的最大值，以及可能导致我们走这条路径的最小值。这使得查看当前值并回答是否可以通过二进制搜索找到的问题变得简单。