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

Question

在给定的排序二进制数组中打印 1 的数量。
例如：

int[] arr = {0,0,0,1,1,1,1};
output : 4
int[] arr = {0,0,1};
output : 1

Answer 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 < 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 1
arr[]: { 0 0 0 1 1 1 1 }
Number of 1 in array :4