解决这个问题的朴素解决方案是在数组中循环并保持数组中出现 1 的计数。
但是当数组被排序时，我们可以停在遇到的第一个，因为当数组被排序时，我们可以确定第一个之后的元素都大于或等于 1，但因为我们的数组包含零和一只有，因此第一个之后的所有元素都将是一个。所以我们的答案是(array.length –currentPointer)。这将处理所有测试用例并在线性O(n)时间内工作。
package Arrays;import java.util.Scanner;public class num1sInsortedbinaryArray { public static void main(String[] args) { Scanner scn = new Scanner(System.in); int[] arr = new int[scn.nextInt()]; for (int i = 0; i < arr.length; i++) { arr[i] = scn.nextInt(); } System.out.println(solve(arr)); } public static int solve(int[] arr) { int currPointer = 0; while (currPointer < arr.length) { if (arr[currPointer] == 1) { // as we have found our first one, we will stop here and // result would be (arr.length-currPinter) break; } // we will keep on increasing currPoniter as long as we are //encountering zeroes currPointer++; } return (arr.length - currPointer); }}我们仍然可以在对数时间内更有效地解决问题，即最坏的时间复杂度为O(log n)。
有效的方法：
我们可以使用分而治之的方法，并在每一步递归移动，通过保持我们的开始和结束指针将数组虚拟地划分为两个子数组。
- 如果子数组结束指针处的元素为零，这意味着该数组中的所有元素都将为零，并且我们知道该数组已经排序。
- 如果第一个元素是数组起始指针处的值怎么办？这意味着该子数组中的所有元素都再次记住数组已排序。
现在让我们讨论时间复杂度。
在每次调用时，我们基本上将要处理的元素数量分成两半。
最初我们有N 个元素，然后是N/2，然后是N/4等等，直到我们剩下一个元素可以使用。
如果我们将处理 n 个元素所花费的时间表示为T(n)。
在数学上，我们可以将方程写为：
T(n) = T(n/2) + T(n/2)T(n/2) = T(n/4) + T(n/4)。..T(2) = T(1) + T(1)
假设我们有 x 个这样的方程，当我们在方程中向上移动时，元素的数量增加了一倍，所以最终，
n = 2^x
在两边取对数，
x = log(n) {to the base 2}因此复杂性我们算法的结果是O(log(n))。
package org.ayush.java2blog;import java.util.Scanner;public class Num1sInSortedBinaryArray { public static void main(String[] args) { Scanner scn = new Scanner(System.in); int[] arr = new int[scn.nextInt()]; for (int i = 0; i < arr.length; i++) { arr[i] = scn.nextInt(); } System.out.print("arr[]: {"); for (int i = 0; i < arr.length; i++) { System.out.print(" "+arr[i]); } System.out.println(" }"); System.out.println("Number of 1 in array :"+solveEfficient(0, arr.length-1, arr)); } public static int solveEfficient(int start, int end, int[] arr) { if (arr[start] == 1) { // start elem is one, hence all other elements will be one in // virtual subarr. return end - start + 1; } if (arr[end] == 0) { // end elem is zero this means, all previous elements of //subarr will be zeroes. return 0; } int mid = (start + end) / 2; int leftResult = solveEfficient(start, mid, arr); int rightResult = solveEfficient(mid + 1, end, arr); // divide the array into two virtual subHalves return leftResult + rightResult; }}当你运行上面的程序时，你会得到下面的输出
7 0 0 0 1 1 1 1arr[]: { 0 0 0 1 1 1 1 }Number of 1 in array :4
