Chinaunix首页 | 论坛 | 博客
  • 博客访问: 754657
  • 博文数量: 104
  • 博客积分: 3715
  • 博客等级: 中校
  • 技术积分: 1868
  • 用 户 组: 普通用户
  • 注册时间: 2006-04-30 08:38
文章分类

全部博文(104)

文章存档

2013年(1)

2012年(9)

2011年(41)

2010年(3)

2009年(3)

2008年(47)

分类: Python/Ruby

2012-05-05 20:27:38

另一个简单的题目from planet scheme.

I’m not sure where this problem comes from; it’s either homework or an interview question. Nonetheless, it is simple and fun:

Take an array of integers and partition it so that all the even integers in the array precede all the odd integers in the array. Your solution must take linear time in the size of the array and operate in-place with only a constant amount of extra space.

Your task is to write the indicated function. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.


我的代码如下:


点击(此处)折叠或打开

  1. #lang racket

  2. ;; find the first element satisfied pred?
  3. (define (find-next pred? vec start)
  4.   (let loop ((index start))
  5.     (if (or (>= index (vector-length vec))
  6.             (pred? (vector-ref vec index)))
  7.         index
  8.         (loop (+ index 1)))))

  9. ;; find the previous element statisfied pred?, exclude start
  10. (define (find-prev pred? vec start)
  11.   (let loop ((index (- start 1)))
  12.     (if (or (< index 0)
  13.             (pred? (vector-ref vec index)))
  14.         index
  15.         (loop (- index 1)))))

  16. (define (eo-partition vec)
  17.   (let loop ((start 0) (end (vector-length vec)))
  18.     (define left (find-next odd? vec start))
  19.     (define right (find-prev even? vec end))
  20.     (if (>= left right)
  21.         vec
  22.         (let ((tmp (vector-ref vec left))
  23.               (nstart (+ left 1))
  24.               (nend (- right 1)))
  25.           (vector-set! vec left (vector-ref vec right))
  26.           (vector-set! vec right tmp)
  27.           (loop nstart nend)))))

阅读(6246) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~
评论热议
请登录后评论。

登录 注册