从包含0和1的排序数组中计算零的数量的算法。

Question

我希望提高我算法的运行时间，算法的目标是计算输入数组中0的总数。输入数组长度为n，由排序好的0和1组成。

目前我的算法是：

Algorithm : zeroCount(A)
Input : An sorted array A containing 0s and 1s
Output : total number of 0s in A

if A[0]=1 then 
    return 0;
len <— A.length
if A[len-1]=0 then
    return len
count <— 0
i <—0
for  i<len do           
    if A[i]==0 then 
        count++
    i++
return count

Java的实现如下：

public int zeroCount(int[] a){

    if(a[0]==1)
    return 0;
    int length =a.length;
    if(a[length-1]==0)
        return length;
    int count=0;
    for(int i=0;i<length&&a[i]==0;i++){
            count++;
    }

    return count;
}

然而，该算法的运行时间为O(n)。如有任何改进该算法以提高运行时间的建议，将不胜感激。

- Bijay Regmi

---

应用二分查找算法。 - DVT

已排序。执行二分搜索以确定0/1转换的位置。 - KathyA.

这可能只是一个练习，但为什么要首先在排序数组中存储0和1？我无法想象这样做的用例。 - JB Nizet

@DVT，您能告诉我如何使用BST吗？ - Bijay Regmi

@BijayRegmi 搜索“二分查找”，阅读并尝试一些东西。 - JB Nizet

@Bijay 我的意思是二分查找，而不是二叉搜索树。请看我的回答。 - Suresh A

Answer 1

由于输入数组已经排序，因此您可以使用二分查找来提高性能。这将使运行时间优化到O(log n)。

使用二分查找的算法是：

Algorithm : zeroCount(A)
Input : sorted array A containing 0s and 1s
Output : total number of 0s in A

if A[0]=1 then 
    return 0;
len <— A.length
if A[len-1]=0 then
    return len
 return  count(A,0,length)


Algorithm : count(A,lower,upper)
Input :  sorted array A , integers lower and upper 
Output : total number of 0s in A

mid <— (lower+upper) / 2

if A[mid] != A[mid-1] then 
    return mid

if A[mid] != A[mid+1] then
    return mid+1

if A[mid] = 1 then 
    return count(A,lower,mid-1)

if A[mid] = 0 then 
       return count(A,mid+1,upper)

Java实现：

public int zeroCount(int[] a) {

    if (a[0] == 1)    // all are 1
        return 0;
    int length = a.length;
    if (a[length - 1] == 0)   //all are 0
        return length;

    return count(a, 0, length);
}

public int count(int[] a, int lower, int upper) {
    int mid = (lower + upper) / 2;
    if (a[mid] != a[mid - 1])   
        return mid;

    if (a[mid] != a[mid + 1])    
        return mid + 1;

    if (a[mid] == 1) {                // all are 1 above mid 
        return count(a, lower, mid - 1);  
    } else if (a[mid] == 0) {              // all are 0 below mid 
        return count(a, mid + 1, upper);  
    }
    return 0;
}

- Suresh A

---

小小的问题：这是一种二分查找，而不是二叉搜索树。二叉搜索树是一种类似树形数据结构，其中子节点根据节点中的数据以某种方式相对于父节点进行排序。 - David Choweller

哦，是的，那只是一个打字错误，我已经更新了我的答案。谢谢@DavidChoweller。 - Suresh A

@Surace，你能告诉我关于基本情况的逻辑吗？ - Bijay Regmi

这个算法的缺陷在于它可能会因为索引值过大而溢出。另外，关于“这将运行时间从O(n)提高到o(n)”，你是不是想说“...提高到O(log n)”？ - Lew Bloch

计数算法实际上是在输入数组中找到0和1之间的转换，正如@KathyA在上面的评论中建议的那样。 - Suresh A

Answer 2

您可以调整二分查找算法来查找数组中最后一个0的位置（比如说，索引为i）。此时0的个数就是（i+1）。

  int CountOfZeroes(int[] A, int key)
        {
            int low = 0;
            int high = A.size - 1;              
            int result = -1;

            while (low <= high)
            {
                int mid = low + (high-low)/2;

                if (A[mid] == key)
                {
                    result = mid;
                    low = mid + 1;
                }
                else if (key < A[mid])
                {
                    high = mid - 1;
                }
                else 
                {
                    low = mid + 1;
                }
            }

            return result + 1;              
        }

您将使用键设置为0调用上述函数。时间复杂度将为O(log n)。

- Bugaboo