将一个数组按某个标准分为两组

最近开始学习《数据结构与算法》这门课程,感觉真就脑筋急转弯...

总感觉脑子里没有想法,我想,应对之策有两个:

  1. 首先得着手开始写,先跑起来再来解决性能问题
  2. 其次就是尽可能发现归纳一些通用的trick

这篇文章是应对之策的第二种的一个例子吧

今天实验课遇到一个题目要求把数组里的奇数放左边,偶数放右边,时间复杂度是O(n)
我一看,噢,这不就是我前段时间心心念念的Quicksort快排算法中第一步,先把数组分两堆么?
步骤我都知道,快排里无非是选定一个数,将它取出,以它做参照,大的放一边,小的放一边么?
这道题里,无非就是简化一下,直接选最右边的数出来,参照标准是mod 2等不等于0

但问题来了,数组要怎么移动呢?
...这就是学习不够深入了,隐约记得取出这个数是挖了个空,然后填坑,最后坑里放回取出的数字,就完事了
问题就出在这个数组移动上
刚开始我想既然o(n),何不直接移到底,遇到偶数往坑里填(坑在最右边),可是留出来的新坑放什么呢?
放偶数?可是不是在左边么
放奇数?好像可行,但是遇到连续几个偶数之后的奇数就麻烦了..
也许这种思路应该摒弃,这种总是对自己代码做什么能不能做好没什么概念,也没什么信心的情况,不知道怎么解决好

一波操作以后,实在不会,上网搜索了一下
发现数组元素的移动是遵循这样一个思路(事实上这道题老师的标准答案也是这个思路)

以这题为例,数组分成左右两边
“左边放奇数,右边放偶数”这句话
其实就等价于
“左边扔掉偶数,右边扔掉奇数”
也就是说,在左边找偶数,在右边找奇数
左右边对应的元素互换就好

因此,设置两个指针指向两边的头,分别对两边进行遍历,直到两个指针碰到一起,代表对整个数组的遍历已经完成
也就是确保了左边全都是奇数,右边全都是偶数

另外一个地方在于怎么选择遍历的顺序,也是其中一个令我迷惑的地方
“左边放奇数,右边放偶数”
最开始取出最右边,那就从左边开始,
左边扔掉一个偶数放坑里,然后坑就在左边了
换到右边遍历,右边扔掉一个奇数放左边,坑就在右边了
如此循环,直到i==j

代码其实很简单,关键是理解这个思路吧,下面是Code

void SeqList::Adjust(){
int left=-1,right=length-1;
int t=data[length-1]; 
int cur=length-1;
while(right!=left){
    while(data[++left]%2!=0&&right!=left);
    data[cur]=data[left];
    cur=left;
    while(data[--right]%2==0&&right!=left);
    data[cur]=data[right];
    cur=right;
}
data[right]=t;
}

我想也许这种转化问题的方法也许是应对之策之三?

标签: none

添加新评论