Java 中的排序二进制数组中 1 的计数

给定一个已排序的二元数组（只包含 0 和 1 的数组是二元数组）。任务是找出二元排序数组中存在的 1 的数量。

示例：1

输入

int arr[] = {0, 0, 0, 0, 1, 1, 1, 1, 1}

输出 5

解释：输入数组中总共有 5 个 1。

示例：2

输入

int arr[] = {0, 0, 0, 0, 0, 0, 0, 0, 0}

输出 0

解释：输入数组中总共有 0 个 1。

朴素方法

在此方法中，我们将使用一个名为 countOne 的变量，并将其初始化为零。然后，我们将使用一个循环来遍历数组的元素。每当循环变量指向的当前元素为 1 时，我们将 countOne 变量加 1。当数组元素遍历完成时，变量 countOne 的值就是我们的答案。请观察以下实现。

文件名： CountOneSortedArray.java

输出

For the input array: 
0 0 0 0 1 1 1 1 1 
The total number of ones is: 5
 
For the input array: 
0 0 0 0 0 0 0 0 0 
The total number of ones is: 0

复杂度分析：由于程序使用了 for 循环，因此程序的时间复杂度为 O(n)，其中 n 是输入数组中的元素总数。程序空间复杂度为常数，即 O(1)。

让我们通过从右到左遍历数组来优化上述程序。这是因为数组是已排序的，所有存在的 1 元素都将位于右侧。因此，我们将只遍历包含值 1 的元素，然后使用 break 语句终止循环。在大多数情况下，以下实现比上面的实现效果更好。只有一种情况，即以下实现和上面的实现具有相同的时间消耗，那就是当输入数组的所有元素的值都为 1 时。

文件名： CountOneSortedArray1.java

输出

For the input array: 
0 0 0 0 1 1 1 1 1 
The total number of ones is: 5
 
For the input array: 
0 0 0 0 0 0 0 0 0 
The total number of ones is: 0

复杂度分析：上面程序使用的循环将只遍历那些值为 1 的元素。因此，程序的时间复杂度为 O(p)，其中 p 是已排序二元数组中存在的 1 的总数。程序空间复杂度与前一个程序相同。

方法：使用二分搜索

由于输入数组已排序，可以使用二分查找来找出输入数组中存在的 1 的总数。

文件名： CountOneSortedArray.java

输出

For the input array: 
0 0 0 0 1 1 1 1 1 
The total number of ones is: 5
 
For the input array: 
0 0 0 0 0 0 0 0 0 
The total number of ones is: 0

复杂度分析：程序使用二分查找，因此程序的时间复杂度为 O(log(n))，其中 n 是输入数组中的元素总数。程序空间复杂度与前一个程序相同。