排序二进制数组中打印 1 的数量

华山汉子

在给定的二进制数组中打印 1 的数量。
例如：
int[] arr = ；output : 4int[] arr = {0，0，1}；output :1
解决方案:
                                                            解决这个问题的简单解决方案是在数组中循环，并在数组中保持 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 我们仍然可以在对数时间内更有效地解决问题，即最坏时间的复杂性是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 当您操作上述程序时，您将获得以下输出
7 00 00 1 1 1 1 arr[]Number of 1 in array :4

排序二进制数组中打印 1 的数量

华山汉子 LV1