讨论：一个Google面经算法题 - JobHunting版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

JobHunting版 - 讨论：一个Google面经算法题

相关主题
● Amazon onsite面经	● 雅虎面经
● 一道面试题	● 求教矩阵改零的问题 (转载)
● median of an array of ints, 请问这题的经典回答是什么？谢谢	● 今天的一个面试题目
● 我想说，我的A家电面，绝对是被烙印黑了，两个45分钟两个烙印	● Print out all elements in a sorted matrix
● 贡献一个groupon的电面题	● 顶风作案，Google面经
● 我花了一个小时才调通过这个程序	● 再上到题
● 问一道数组题	● 找杨氏矩阵的第k大的数?
● search in a rotated array	● Ebay三电面，攒人品

相关话题的讨论汇总
话题: 矩阵话题: 每一话题: google话题: 递增话题: 一列

进入JobHunting版参与讨论

(共1页)

d********y
发帖数: 93

input是一个2D的整数矩阵，output是一个满足下面要求的矩阵：
1. 矩阵每一行从左到右递增(含相等)、每一列从上到下依次递增(含相等)
2. 矩阵每一行不能出现相同的数字
举例：
如果input是
1 3 4
2 3 5
那么output可以是：
1 3 4
2 3 5
或者
1 2 3
3 4 5
或者
1 3 4
2 3 5
等任何一种
一种行得通的做法是先将所有元素加到Heap里面，然后一列一列地填，每一列都按从上
往下的顺序填。但这个复杂度是N * lg N，这里N是矩阵的元素个数。
有更优的方法吗？

b********6
发帖数: 35437

用radix sort怎么样O(n)，读出来O(n), 排序O(n)，写回去O(n)
其实n log n已经够了吧，如果这个矩阵只有一行，就是数组排序，n log n就不错了。

(共1页)

进入JobHunting版参与讨论

相关主题
● Ebay三电面，攒人品	● 贡献一个groupon的电面题
● 问一道题(3)	● 我花了一个小时才调通过这个程序
● 一道大数据的题，讨论一下	● 问一道数组题
● 求帮忙解答一个面试算法题==	● search in a rotated array
● Amazon onsite面经	● 雅虎面经
● 一道面试题	● 求教矩阵改零的问题 (转载)
● median of an array of ints, 请问这题的经典回答是什么？谢谢	● 今天的一个面试题目
● 我想说，我的A家电面，绝对是被烙印黑了，两个45分钟两个烙印	● Print out all elements in a sorted matrix

相关话题的讨论汇总
话题: 矩阵话题: 每一话题: google话题: 递增话题: 一列

#	版面	帖数(主题数)
-	全站	4871 (796)
1	Military	3777 (569)
2	Stock	341 (51)
3	Joke	117 (17)
4	History	116 (3)
5	Automobile	100 (9)
6	USANews	55 (9)
7	Midlife	45 (1)
8	Headline	41 (41)
9	Dreamer	33 (13)
10	FleaMarket	32 (20)
11	Living	30 (7)

boards

未名新帖统计// 7月16日

历史上的今天