[算法]数组的partition调整

题目一：

给定一个有序数组arr，调整arr使得这个数组的左半部分没有重复部分且升序，而不用保证右部分是否有序。

例如：arr=[1,2,2,2,3,3,4,5,6,6,7,7,8,8,9,9]，调整之后arr=[1,2,3,4,5,6,7,8,9…]。

要求：

时间复杂度O(N),额外空间复杂度O(1)

程序：

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);

			}

		}

	}

题目二：

给定一个数组arr，其中只可能含有0、1、2三个值，请实现arr的排序。

另外一种问法：有一个数组，其中只有红球、篮球和黄球，请实现红球全放在数组的左边，篮球放在中间，黄球放在右边。

另外一种问法：有一个数组，再给定一个值K，请实现比K小的数都放在数组的左边，等于K的值都放在数组的中间，比K大的数都放在数组的右边。

程序：

	public static void sort(int[] arr) {

		if (arr == null || arr.length < 2) {

			return;

		}

		int left = -1;

		int index = 0;

		int right = arr.length;

		while (index < right) {

			if (arr[index] == 0) {

				swap(arr, ++left, index++);

			} else if (arr[index] == 2) {

				swap(arr, index, --right);

			} else {

				index++;

			}

		}

	}

巴特西

[算法]数组的partition调整

题目一：

要求：

程序：

题目二：

程序：

最新文章

热门文章