c******t
发帖数: 391 | 1 在别人面经里看到下面一道题，
Given a character array with space separated words, how to sort the words in
place?
For example:
input: char[] = {'c','a', 't', ' ', ,'d', 'o', 'g', ' ', 'b', 'o', 'y'};
output: result: {'b', 'o', 'y', ' ', 'c', 'a', 't', ' ', 'd','o', 'g'}
目前能想到的解法就是把数组split成单词String，写一个comparator排序之，再存入
另一个result char array，但这样就不是in-place了。。。
求教... | L***s
发帖数: 1148 | 2 我会先考虑一个特殊情况：如果只有两个words被一个空格隔开，如何in-place排序？
解决了这个问题，就可以解决N>2个words的情形，在word的层面冒泡排序，
每次交换的时候应用上述特殊情形。
这是我的第一感觉。也许有更高效的办法。
in
【在 c******t 的大作中提到】
: 在别人面经里看到下面一道题，
: Given a character array with space separated words, how to sort the words in
: place?
: For example:
: input: char[] = {'c','a', 't', ' ', ,'d', 'o', 'g', ' ', 'b', 'o', 'y'};
: output: result: {'b', 'o', 'y', ' ', 'c', 'a', 't', ' ', 'd','o', 'g'}
: 目前能想到的解法就是把数组split成单词String，写一个comparator排序之，再存入
: 另一个result char array，但这样就不是in-place了。。。
: 求教...
| i******s
发帖数: 301 | | m*****n
发帖数: 2152 | 4 如果词的长度可以不一样，怎么快排？
【在 i******s 的大作中提到】
: 直接写一个快排
| c******t
发帖数: 391 | 5 恩，词的长度是可以不一样的。同问快排解法思路... | h**********c
发帖数: 4120 | 6 我觉得首先根据wikipedia sorting algorithm 一章
sorting input data should allow random access,这个题的input data并不满足这个
条件。所以用现有的sorting 方法，或者说这根本不是一个sorting 算法category的问
题。 | m*****n
发帖数: 2152 | 7 bubble sort 可以不要random access啊。而且这道题的目前能想到的解法就是bubble
sort。
【在 h**********c 的大作中提到】
: 我觉得首先根据wikipedia sorting algorithm 一章
: sorting input data should allow random access,这个题的input data并不满足这个
: 条件。所以用现有的sorting 方法，或者说这根本不是一个sorting 算法category的问
: 题。
| h**********c
发帖数: 4120 | 8 bubbling definite will solve the problem.
But if you switch two words, may be the whole array has to shift. Not sure,
this will cause n^3 worst case.
bubble
【在 m*****n 的大作中提到】
: bubble sort 可以不要random access啊。而且这道题的目前能想到的解法就是bubble
: sort。
| n******n
发帖数: 12088 | 9 加个限制，字长最多是k
,
【在 h**********c 的大作中提到】
: bubbling definite will solve the problem.
: But if you switch two words, may be the whole array has to shift. Not sure,
: this will cause n^3 worst case.
:
: bubble
| c******t
发帖数: 391 | 10 Could you explain on the shift part?
Thanks!
,
【在 h**********c 的大作中提到】
: bubbling definite will solve the problem.
: But if you switch two words, may be the whole array has to shift. Not sure,
: this will cause n^3 worst case.
:
: bubble
|
|
