当前位置: 首页 > 面试题库 >

对 0s、1s 和 2s 的数组进行排序

訾雅畅
2023-03-14
问题内容

给定一个只包含零、一和二的数组。编写一个函数来按O(n)时间复杂度对给定数组进行排序。

Input :
[1, 2, 2, 0, 0, 1, 2, 2, 1]
Output :
[0, 0, 1, 1, 1, 2, 2, 2, 2]
[0, 0, 1, 1, 1, 2, 2, 2, 2]

问题答案:

方法 – I :
解决这个问题的一个非常基本的方法是保持给定数组中零、一和二的数量的计数,然后根据每个数字的频率操作给定的数组。这种方法有点受计数排序的启发。无论该特定索引的初始值是什么,我们首先将数组中的所有零从索引零开始放入,然后放入所有的 1,然后放入所有的 2。

步骤:
1.) 遍历给定数组一次并不断增加遇到的数字的计数。
2.) 现在再次从索引零开始遍历数组,并不断更改当前索引上元素的值,首先耗尽所有零,然后是 1,最后是所有 2。

这样我们就有了一个排序的数组,其中所有的零都在开始,然后是所有的 1,然后在最后一节中,我们在时间复杂度为. O(n)

但这种方法的主要缺点是,我们必须遍历给定数组两次以计算零、一和二的数量,第二次遍历数组以对其进行排序,这只能在一次通过中完成。

  package Arrays;

    public class sort012 {

    public static void main(String[] args) {

        int[]a = {1,0,2,0,0,1,2,2,1};
        sort(a);
        for(int val : a)
        {
            System.out.println(val + " ");
        }

    }
    /*Function to sort the given array*/
    public static void sort(int[]a)
    {
        /* array to keep the count of 0s, 1s, 2s*/
        int[]freq = new int[3];

        /* traverse the given array for filling the
         * frequency array*/
        for(int val : a)
        {
            freq[val]++;
        }
        /*pointer to traverse the given array again*/
        int pointer = 0;
        for(int i=0;i<freq.length;i++)
        {
            /* loop to exhaust the number of 0s, 1s, 2s*/
            while(freq[i]-->0)
            {
                /*at the current pointer plot the current number*/ 
                a[pointer]=i;
                /*increment the pointer*/
                pointer++;
            }
        }
    }

方法 – II :
这种算法被称为Dutch national flag algorithm 或 Three way partitioning其中相似类型的元素被分组在一起,并且它们的集合组也以正确的顺序排序。
现在我们有三种类型的元素要排序,因此,我们将给定的数组分为四个部分,其中 3 个部分被指定为zeroes,Ones和twos分别有一个部分是unknown或留下待探索的部分。现在为了遍历这些部分,我们还需要 3 个指针,它们实际上将给定的数组分成四段。
让我们将这些指针命名为低、中和高。
现在我们可以分辨出这些段的起点和终点。

Segment-1 : zeroes
这将是一个已知部分,仅zeroes包含范围为[0, low-1].
Segment-2: Ones
这也是一个知道部分,只包含范围为 的部分[low, mid-1]。
Segment-3 : Unexplored
这将是一个未知部分,因为该部分中的元素尚待探索,因此它可以包含所有类型的元素,即零、一和二。该段的范围将是[mid, high]
Segment-4:Twos
这将是最后一个已知区域,只包含范围为[high+1, N]N 是给定数组的长度或基本上给定数组的最后一个有效索引的二进制数。
此算法中用于在单次传递中对给定数组进行排序的步骤:

(I)初始化低,中,高指针,low = 0,mid = 0,high = N
(II)现在,运行一个循环并执行以下操作,直到mid指针最终满足highpointer.As的mid指针向前移动,我们一直把该元素的mid指针,它的正确位置通过将该元素与相应部分的指针处的元素交换。
(ⅲ)CASE - I:如果在所述元素mid,也就是A[mid] ==0,此装置该元件的正确位置在上述范围内[0,low-1],因此,我们交换A[mid]与A[low] 和增量低确保元件与指数大于低较小是零。
(iv) CASE – II:如果元素在mid,即,A[mid]==2,此手段该元件的正确位置在上述范围内[hi+1, N],因此,我们交换A[mid]与A[hi]和递减高确保具有指数大于高元件是一个两决策。
(v) CASE – III :如果元素在中间,即A[mid]=1,这意味着该元素已经在它的正确段中,因为它[low, mid-1]是它需要的范围。因此,我们什么都不做,只是简单地增加中间指针。

所以,总共有三种情况,让我们花点时间强调一个事实,即中指针仅在元素A[mid] == 1.
让我们单独讨论每个案例,

对于情况-我 :在这种情况下,我们增加mid以及随着增量low指针,因为我们相信,在交换前低指针元素可以肯定只有一个因为它当时两个,就已经得到了交换与high指针,当mid指针探索它作为中指针离开它的唯一原因,因为它是一个。

对于情况- II:现在,在这种情况下,我们交换位置的元素mid和high,但与案例-我,在这种情况下,我们不知道它会在元素mid在交换的元素之后指数high索引之前交换可以是任何零,一或两个,因此,我们需要探索这个交换的元素,因此mid在这种情况下我们不增加指针。

对于情况 – III:mid在这种情况下,正如已经讨论过的那样,关于递增没有混淆,因为我们知道元素 atmid是 1,因此我们肯定需要在这里递增 mid。

该算法的时间复杂度也是O(n),但它只需一次遍历即可对数组进行排序,并且与以前的方法不同,没有任何额外的空间。

  package Arrays;

    public class sort012 {

    public static void main(String[] args) {

        int[]a = {1,2,2,0,0,1,2,2,1};
        sort(a);
        for(int val : a)
        {
            System.out.print(val + " ");
        }

    }

    public static void sort(int[]a)
    {
        /* Three pointers to divide the array in designated segments
         * as discussed in the post*/
        int low=0,mid=0,high=a.length-1;
        while(mid<=high)
        {
            /* Case - 1, when element at mid pointer is zero,
             * swap with element at low*/
            if(a[mid]==0)
            {
                a[low]=swap(a[mid], a[mid]=a[low]);
                /* Increment low as well as mid, as we know
                 * the swapped element at mid is a one*/
                low++;
                mid++;
            }
            /* Case - 1, when element at mid pointer is two,
             * swap with element at high*/
            else if(a[mid]==2)
            {
                /* decrement only high and keep mid unchanged, as
                 * we do not know anything about the swapped element
                 * at mid*/
                a[high]=swap(a[mid],a[mid]=a[high]);
                high--;
            }
            else {
                /*Case - 3, when element at mid pointer is one*/
                /*do nothing, and increment mid pointer*/
                mid++;
            }

        }
    }

    /* utility swap function*/
    public static int swap(int i, int j)
    {
        return i;
    }
}

那是关于对 0、1 和 2 的数组进行排序。



 类似资料:
  • 主要内容:算法总结及实现,优化算法在实际开发中,有很多场景需要我们将数组元素按照从大到小(或者从小到大)的顺序排列,这样在查阅数据时会更加直观,例如: 一个保存了班级学号的数组,排序后更容易分区好学生和坏学生; 一个保存了商品单价的数组,排序后更容易看出它们的性价比。 对数组元素进行排序的方法有很多种,比如冒泡排序、归并排序、选择排序、插入排序、快速排序等,其中最经典最需要掌握的是「冒泡排序」。 以从小到大排序为例,冒泡排序的整体

  • 部分排序可以通过std::Partial_sort完成。 部分排序方式 5 7 4 2 8 6 1 9 0 3 在对3个元素进行部分排序之后 0 1 2 7 8 6 5 9 4 3 http://en.cppreference.com/w/cpp/algorithm/partial_sort. 但当某些元素已经排序时,这不是最好的。 还有其他这样的函数可以这样做并利用部分排序数组。

  • 我希望根据记录的整数值降序排序:

  • 问题内容: 我想对整数的arraylist的arraylist进行排序,需要帮助吗? 我被告知,我需要实现比较器或可比对象,然后使用collection.sort对列表列表进行排序… 问题答案: 没有错误检查空列表,但是这里是。 使用Java 8,它变得更加简洁:

  • 本文向大家介绍java对数组进行排序的方法,包括了java对数组进行排序的方法的使用技巧和注意事项,需要的朋友参考一下 本文实例讲述了java对数组进行排序的方法。分享给大家供大家参考。具体如下: 执行结果: 排序前:  12 24 25 4 9 68 45 7   排序后:  4 7 9 12 24 25 45 68 希望本文所述对大家的java程序设计有所帮助。

  • 我有一个过程对象列表,如下所示 我的程序课就像 我想基于以下条件对对象进行排序和分组。 应根据过程名称对所有过程进行分组。 过程必须按过程日期降序排列。[日期列表中的第一个元素,即 分组在一起的相同过程应按日期降序排列。 最终结果必须是, 我能够使用比较器和旧的Java代码实现这一点。是否可以使用java8流、收集器和分组来实现相同的功能?