查看: 2404|回复: 7
收起左侧

Microsoft : One special sort problem

|只看干货 |刷题
头像被屏蔽

分享帖子到朋友圈
wwwyhx | 显示全部楼层 |阅读模式
提示: 作者被禁止或删除 内容自动屏蔽

上一篇:Microsoft : Create two evenly balanced teams for a game of soccer.
下一篇:Microsoft : find the next biggest node in a BST
Roquin 2011-5-29 23:53:33 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎
如果全是正数的话,比较的时候奇数加个符号,按升序排就可以了吧
回复

使用道具 举报

头像被屏蔽
 楼主| wwwyhx 2011-5-31 13:14:36 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

头像被屏蔽
burself 2011-10-31 01:23:42 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

头像被屏蔽
burself 2011-10-31 01:26:17 | 显示全部楼层
提示: 作者被禁止或删除 内容自动屏蔽
回复

使用道具 举报

xiaozhuzi27 2012-1-30 11:58:31 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (4)
 
 
0% (0)    👎
不能有pre or post processing。。。难道是奇偶和排序在遍历的时候同时进行么?
我觉得先把奇偶分出来挺靠谱的啊。。。
回复

使用道具 举报

wwwzj30 2012-2-1 06:33:57 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (2)
 
 
0% (0)    👎
Use quick sort. When comparing numbers any odd number is presented as its negative. O(N log N)
This is equivalent to:
1. Preprocess an array so that all odd numbers are negative to the original
2. Sort the whole array
3. Post-process the array so that all odd numbers are negative to the current (which are all negative)

For example
1234567
when comparing, all odd numbers are in its negative presentation
-1 2 -3 4 -5 6 -7
After Sort:
-7 -5 -3 -1 2 4 6
But the number itself is not actually inverted
7 5 4 1 2 4 6

It fits the requirement of top portion of the array contains odd numbers, bottom portion contains even numbers. The odd numbers are to be sorted in descending order and the even numbers in ascending order.
回复

使用道具 举报

ilnlh 2012-2-27 13:18:59 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (224)
 
 
0% (1)    👎
bubble sort (sentinel at index 0):
  1. def bsort(l):
  2.   n = len(l) - 1
  3.   while n > 1:
  4.     l[0] = l[1]
  5.     i = 1
  6.     while i < n:
  7.       left = l[i]
  8.       right = l[i + 1]
  9.       if left % 2 == 0 and right % 2 == 1 or \
  10.           (left % 2 == 0 and right % 2 == 0 and right < left) or \
  11.           (left % 2 == 1 and right % 2 == 1 and left < right):
  12.         l[0] = l[i + 1]
  13.         l[i + 1] = l[i]
  14.         l[i] = l[0]
  15.       i += 1
  16.     if l[0] == l[1]:
  17.       break
  18.     n -= 1
复制代码
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://tools.1point3acres.com/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

>
快速回复 返回顶部 返回列表