【简单】数组的partition调整－Java：原问题

分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请轻击人工智能教程大家好！欢迎来到我的网站！ 人工智能被认为是一种拯救世界、终结世界的技术。毋庸置疑，人工智能时代就要来临了，科… 继续阅读 前言https://www.captainai.net/troubleshooter

package live.every.day.ProgrammingDesign.CodingInterviewGuide.ArrayAndMatrix; import java.util.Arrays; /** * 数组的partition调整 * * 【题目】 * 给定一个有序数组arr，调整arr使得这个数组的左半部分没有重复元素且升序，而不用保证右部分是否有序。 * 例如，arr=[1,2,2,2,3,3,4,5,6,6,7,7,8,8,8,9]，调整之后arr=[1,2,3,4,5,6,7,8,9,...]。 * * 【补充题目】 * 给定一个数组arr，其中只可能含有0、1、2三个值，请实现arr的排序。 * 另一种问法为：有一个数组，其中只有红球、蓝球和黄球，请实现红球全放在数组的左边，蓝球放在中间，黄球放在右边。 * 另一种问法为：有一个数组，再给定一个值k，请实现比k小的数都放在数组的左边，等于k的数都放在数组的中间，比k大的数都放在数 * 组的右边。 * * 【要求】 * 1.所有题目实现的时间复杂度为O(N)。 * 2.所有题目实现的额外空间复杂度为O(1)。 * * 【难度】 * 简单 * * 【解答】 * 先来介绍原问题的解法： * 1.生成变量u，含义是在arr[0..u]上都是无重复元素且升序的。也就是说，u是这个区域最后的位置，初始时u=0，这个区域记为A。 * 2.生成变量i，利用i做从左到右的遍历，在arr[u+1..i]上是不保证没有重复元素且升序的区域，i是这个区域最后的位置，初始时 * i=l，这个区域记为B。 * 3.i向右移动(i++)。因为数组整体有序，所以如果arr[i]!=arr[u]，说明当前数arr[i]应该加入到A区域里，所以交换arr[u+1] * 和arr[i]，此时A的区域增加一个数(u++)；如果arr[i]==arr[u]，说明当前数arr[i]的值之前已经加入到A区域，此时不用再加 * 入。 * 4.重复步骤3，直到所有的数遍历完。 * 具体请参看如下代码中的leftUnique方法。 * * @author Created by LiveEveryDay */ public class ArrayPartitionAdjustment1 { public static void leftUnique(int[] arr) { if (arr == null || arr.length < 2) { return; } int u = 0; int i = 1; while (i != arr.length) { if (arr[i++] != arr[u]) { swap(arr, ++u, i - 1); } } } private static void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; } public static void main(String[] args) { int[] arr = {1, 2, 2, 2, 3, 3, 4, 5, 6, 7, 7, 8, 8}; leftUnique(arr); System.out.printf("The array is: %s", Arrays.toString(arr)); } } // ------ Output ------ /* The array is: [1, 2, 3, 4, 5, 6, 7, 8, 3, 2, 7, 2, 8] */