专栏首页Jed的技术阶梯[算法题] 荷兰国旗问题

[算法题] 荷兰国旗问题

1. 问题描述

荷兰国旗是由红白蓝3种颜色的条纹拼接而成,如下图所示:

假设这样的条纹有多条,且各种颜色的数量不一,并且随机组成了一个新的图形,新的图形可能如下图所示,但是绝非只有这一种情况:

需求是:把这些条纹按照颜色排好,红色的在上半部分,白色的在中间部分,蓝色的在下半部分,我们把这类问题称作荷兰国旗问题。

我们把荷兰国旗问题用数组的形式表达一下是这样的:

给定一个整数数组,给定一个值K,这个值在原数组中一定存在,要求把数组中小于K的元素放到数组的左边,大于K的元素放到数组的右边,等于K的元素放到数组的中间,最终返回一个整数数组,其中只有两个值,分别是等于K的数组部分的左右两个下标值。

例如,给定数组:[2, 3, 1, 9, 7, 6, 1, 4, 5],给定一个值4,那么经过处理原数组可能得一种情况是:[2, 3, 1, 1, 4, 9, 7, 6, 5],需要注意的是,小于4的部分不需要有序,大于4的部分也不需要有序,返回等于4部分的左右两个下标,即[4, 4]

2. 处理过程图示

我们以上面举的例子来看看处理过程的图示:

image.png

  • less 用于记录小于 4 的区域的右下标,初始为-1,代表不存在
  • more 用于记录大于 4 区域的左下标,初始为9,代表不存在
  • L 用于正在遍历的元素的下标,初始值为0
  • 从 arr[L] 即 arr[0] 开始遍历数组
    • 如果 arr[L] > 4, 交换 arr[++ less] 和 arr[L++] 的值
    • 如果 arr[L] < 4, 交换 arr[--more] 和 arr[L] 的值
    • 如果 arr[L] = 4, 不交换,L++,直接遍历下一个值
  • 当 L >= more,退出循环。

3. Java代码实现

public static int[] partition(int[] arr, int L, int R, int p) {
    int less = L - 1;
    int more = R + 1;
    while(L < more) {
        if(arr[L] < p) {
            swap(arr, ++less, L++);
        } else if (arr[L] > p) {
            swap(arr, --more, L);
        } else {
            L++;
        }
    }
    return new int[] { less + 1, more - 1 };
}

public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • [图解] 堆排序

    大根堆与数组的关系:计算机中是没有堆或者树这种概念的,堆或者树需要使用基本的数据结构来实现,用数组表示一个大根堆的规律如下:

    CoderJed
  • [图解] 快速排序

    经典快速排序总是指定数组或者某部分的最后一个元素作为基准值,随机快速排序指定数组或者某一部分中的随机值作为基准值。

    CoderJed
  • Hadoop伪分布式集群搭建

    CoderJed
  • 如何实现归并排序?

    划分步骤很简单:将当前数组分成两半(如果N是偶数,则将其完全平等,或者如果N是奇数,则一边稍大于一个元素),然后递归地对这两半进行排序。

    行百里er
  • 寻找数组中第二小的元素

    一觉睡到小时候
  • java基础学习_基础语法(下)01_day05总结

    ============================================================================= ==...

    黑泽君
  • [图解] 堆排序

    大根堆与数组的关系:计算机中是没有堆或者树这种概念的,堆或者树需要使用基本的数据结构来实现,用数组表示一个大根堆的规律如下:

    CoderJed
  • 【Java】04 数组

    初始化:   静态初始化:初始化时由程序员显式指定每个数组元素的初始值,由系统决定数组长度。   动态初始化:初始化时程序员只指定数组长度,由系统为数组元素...

    Demo_Null
  • 求解连续子数组和全解析-常规解法VS树状数组!

    本文将介绍几求解数组前缀和和连续子数组和的三种方法,分别是遍历法、辅助数组法、树状数组法。

    石晓文
  • LeetCode 769. 最多能完成排序的块

    数组arr是[0, 1, ..., arr.length - 1]的一种排列,我们将这个数组分割成几个“块”,并将这些块分别进行排序。 之后再连接起来,使得连...

    Michael阿明

扫码关注云+社区

领取腾讯云代金券