(3/500)在线性时间内对二进制数组排序

发布时间:2017-5-19 8:56:40编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"(3/500)在线性时间内对二进制数组排序",主要涉及到(3/500)在线性时间内对二进制数组排序方面的内容,对于(3/500)在线性时间内对二进制数组排序感兴趣的同学可以参考一下。

给定一个二进制数组(数组元素是0和1),请对数组进行排序,要求时间复杂度为O(n),空间复杂度为O(1)。输出内容应该是所有的0在前,之后是所有的1。
例如,
输入:{ 1, 0, 1, 0, 1, 0, 0, 1 }
输出:{ 0, 0, 0, 0, 1, 1, 1, 1 }

 

1. 傻瓜式方法

一种简单的方法是计算数组中0的个数(假设为k),然后把数组的前k个元素置为0,其他的置为1。同样道理,也可以计算1的个数(假设为k),然后把前面的k个元素置为1,其他的置为0。二者选一即可。实现方式比较简单,代码就省略了。

 

2. 填充0的另一种想法

和计算0的个数相比,我们可以换种方法。如果当前元素是0,我们可以把0放到下一个可用的位置。在所有的元素都处理了之后, 把其它所有的元素都置为1。

C++语言实现:

#include <bits/stdc++.h>
using namespace std;
 
// Function to sort binary array in linear time
int Sort(int A[], int n)
{
    // k stores index of next available position
    int k = 0;
 
    // do for each element
    for (int i = 0; i < n; i++)
    {
        // if current element is zero, put 0 at next free
        // position in the array
        if (A[i] == 0)
            A[k++] = 0;
    }
 
    // fill all remaining indexes by 1
    for (int i = k; i < n; i++)
        A[k++] = 1;
}
 
// main function
int main()
{
    int A[] = { 0, 0, 1, 0,1, 1, 0, 1, 0, 0 };
    int n = sizeof(A)/sizeof(A[0]);
 
    Sort(A, n);
 
    // print the rearranged array
    for (int i = 0 ; i < n; i++)
        cout << A[i] << " ";
 
    return 0;
}
java语言实现:

class SortBinaryArray
{
    // Function to sort binary array in linear time
    public static void Sort(int A[], int n)
    {
        // k stores index of next available position
        int k = 0;
 
        // do for each element
        for (int i = 0; i < n; i++)
        {
            // if current element is zero, put 0 at next free
            // position in the array
            if (A[i] == 0)
                A[k++] = 0;
        }
 
        // fill all remaining indexes by 1
        for (int i = k; i < n; i++)
            A[k++] = 1;
    }
 
    // main function
    public static void main (String[] args)
    {
        int A[] = { 0, 0, 1, 0, 1, 1, 0, 1, 0, 0 };
        int n = A.length;
 
        Sort(A, n);
 
        // print the rearranged array
        for (int i = 0 ; i < n; i++)
            System.out.print(A[i] + " ");
    }
}

输出: 0 0 0 0 0 0 1 1 1 1

以上两种方案的时间复杂度都是O(n),空间复杂度都是o(1)。

 

3. 基于快速排序分而治之的算法

除了以上两种方法,我们还可以借用快速排序中分而治之的思想。这种方法的关键是使用1作为主元素(pivot element),然后创建一个分区过程,最后的结果就是排好序的。

C++语言实现:

#include <bits/stdc++.h>
using namespace std;
 
// Function to sort binary array in linear time
int Partition(int A[], int n)
{
    int pivot = 1;
    int j = 0;
 
    // each time we encounter a 0, j is incremented and
    // 0 is placed before the pivot
    for (int i = 0; i < n; i++)
    {
        if (A[i] < pivot)
        {
            swap(A[i], A[j]);
            j++;
        }
    }
}
 
// main function
int main()
{
    int A[] = { 1, 0, 0, 0, 1, 0, 1, 1 };
    int n = sizeof(A)/sizeof(A[0]);
 
    Partition(A, n);
 
    // print the rearranged array
    for (int i = 0 ; i < n; i++)
        cout << A[i] << " ";
 
    return 0;
}

java语言实现:

class SortBinaryArray
{
    // Function to sort binary array in linear time
    public static void Sort(int A[], int n)
    {
        int pivot = 1;
        int j = 0;
 
        // each time we encounter a 0, j is incremented and
        // 0 is placed before the pivot
        for (int i = 0; i < n; i++)
        {
            if (A[i] < pivot)
            {
                // swap (A[i], A[j])
 
                int temp = A[i];
                A[i] = A[j];
                A[j] = temp;
 
                j++;
            }
        }
    }
 
    // main function
    public static void main (String[] args)
    {
        int A[] = { 0, 0, 1, 0, 1, 1, 0, 1, 0, 0 };
        int n = A.length;
 
        Sort(A, n);
 
        // print the rearranged array
        for (int i = 0 ; i < n; i++)
            System.out.print(A[i] + " ");
    }
}

输出: 0 0 0 0 0 0 1 1 1 1

尽管以上各种方法时间复杂度是O(n),空间复杂度是O(1),明显第三种方法的时间更少。

 

4. 通过首尾两个索引排序

我还能想到另外一种解决方案,新建两个索引分别指向首尾(head 和 end),向中间聚拢,当head指向的数字不为0,并且end指向的数字不为1时,交换它们的位置,直到head大于或等于end。

闲话少说,上代码。偷一下懒,我就只写Java代码了。

public class SortBinaryArray2 {
 
    // Function to sort binary array in linear time
    public static void Sort(int A[], int n)
    {
        int head = 0;
        int end = A.length - 1;
 
        while( head < end )
        {
            while( A[head] == 0 && head < A.length -1 )
            {
                head ++;
            }
            while( A[end] == 1 && end > 0 )
            {
                end --;
            }
            if( head >= end )
            {
                break;
            }
            int temp = A[head];
            A[head] = A[end];
            A[end] = temp;
        }
    }
 
    public static void main(String[] args) {
            int A[] = { 0, 0, 1, 0, 1, 1, 0, 1, 0, 0 };
            int n = A.length;
 
            Sort(A, n);
 
            // print the rearranged array
            for (int i = 0 ; i < n; i++)
            {
              System.out.print(A[i] + " ");
            }
    }
}

这种方法是不是更省时? ^_^

 

练习:
1. 在原方案的基础上修改方案,把1放在前面。
2. 给定一个数组,在线性时间内(时间复杂度为O(n))排序,使所有的偶数排在奇数之前。




上一篇:MySQL递归查询树状表的子节点、父节点具体实现
下一篇:SIFT算法详解

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款