这题有啥好解法？可以o(n)实现吗？

数组乱序，给一个target, reorder成3部分，
{小于某数，等于某数，大于某数}，小于某数的数们排前面，他们之间可以乱序。大于某数的数们排后面，他们之间可以乱序。

我弄了下，好像没法一次遍历 o（n)实现reorder

你听说过pivot嘛，一次partition就是实现了比pivot小的在左边，比pivot大的在右边。
是quickSort的核心算法

简单，双指针，头尾各一个，遇到比这个大的往尾部塞，比这个小的往有头部塞，遇到满足条件的的指针往相应方向移一位。

红A 发表于 2021-1-1 04:04
你听说过pivot嘛，一次partition就是实现了比pivot小的在左边，比pivot大的在右边。
是quickSort的核心算 ...

多谢

已经写完代码了

这个题很像sort colors那道 可以看一下sort colors 的解法

3路快排的核心实现。O(n)可以

这不就是LC sort colors那个题吗？

momo19157 发表于 2021-1-1 04:39
这不就是LC sort colors那个题吗？

原题的变种

三路快排

https://leetcode.com/problems/sort-colors/

quick sort了解一下