数组分区—荷兰国旗问题?

简介: 数组分区—荷兰国旗问题?

给定一个数组arr,和一个整数num,将数组分为三段,[< | = | >]。把小于num的数放在数组左边,等于num的数放在中间,大于num的数放在右边,小于部分和大于部分可以无序。——经典的荷兰国旗问题。

但是以下代码实现方式是以数组最后一个元素作为num,所以本题就是一个经典的荷兰国旗划分三色问题

package com.harrison.class03;
public class Code04_Netherlands {
  public static int[] netherlands(int[] arr, int L, int R) {
    if (L > R) {
      return new int[] { -1, -1 };
    }
    if (L == R) {
      return new int[] { L, R };
    }
    int less = L - 1;
    int more = R;
    int i = L;
    while (i < more) {
      if (arr[i] == arr[R]) {
        i++;
      } else if (arr[i] < arr[R]) {
        swap(arr, i++, ++less);
      } else {
        swap(arr, i, --more);
      }
      // L...less less+1...more-1 more...R-1 R
      // L...less less+1..........more more+1...R
      swap(arr, more, R);
    }
    return new int[] { less + 1, more };
  }
  public static void swap(int[] arr, int i, int j) {
    int t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
  }
  public static void main(String[] args) {
    int[] arr= {9,32,3,4,-3,4,3,90,-3,9};
    int[] ans=netherlands(arr, 0, arr.length-1);
    for(int i=0; i<ans.length; i++) {
      System.out.print(ans[i]+" ");
    }
    // -3 -3 3 3 4 4 | 9 9 | 32 90
    // 6,7
  }
}

相关文章
|
10月前
|
存储
【每日一题Day275】LC771宝石与石头 | 哈希表 状态压缩
【每日一题Day275】LC771宝石与石头 | 哈希表 状态压缩
55 0
|
9月前
|
存储
【海贼王的数据航海】顺序表
【海贼王的数据航海】顺序表
41 0
|
9月前
【海贼王的数据航海】栈和队列
【海贼王的数据航海】栈和队列
48 0
|
10月前
【每日一题Day298】LC13883n 块披萨 | 动态规划之打家劫舍
【每日一题Day298】LC13883n 块披萨 | 动态规划之打家劫舍
64 0
|
10月前
【每日一题Day124】LC2347最好的扑克手牌 | 哈希表
【每日一题Day124】LC2347最好的扑克手牌 | 哈希表
53 0
|
算法
山东第一届省赛 Greatest Number(优雅暴力+二分)
山东第一届省赛 Greatest Number(优雅暴力+二分)
93 1
575. 分糖果【我亦无他唯手熟尔】
575. 分糖果【我亦无他唯手熟尔】
67 0
[蓝桥杯 2016 省 B] 交换瓶子
[蓝桥杯 2016 省 B] 交换瓶子
74 0
|
机器学习/深度学习 人工智能
【第十五届蓝桥杯备赛(bushi,写文凑个数)】蓝桥OJ---排列序数
文章目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 三、知识风暴 DFS
125 0
|
C++
【力扣·每日一题】807. 保持城市天际线(C++ 贪心)
【力扣·每日一题】807. 保持城市天际线(C++ 贪心)
118 0
【力扣·每日一题】807. 保持城市天际线(C++ 贪心)

热门文章

最新文章