由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 问一道老题
相关主题
一个小公司面经一个特别的inplace merge two sorted arrays
请教一道题目[算法] unsorted array
Google电话面试题目Search in a sorted, rotated list
A家面试题Given an array of N integers from range [0, N] and one is missing. Find the missing number.
请问这题是什么意思[合集] Google电话面试题目
这题怎么做?a[i] + b[j] = c[k] 的题有靠谱的答案不?
median of an array of ints, 请问这题的经典回答是什么?谢谢请教个面试题
请教一道L的题Groupon 電面
相关话题的讨论汇总
话题: elements话题: array话题: give话题: given话题: sort
进入JobHunting版参与讨论
1 (共1页)
I***A
发帖数: 6
1
Given an array A of n elements and an integer k (where k ]...A[k]}and {A[k+1]...A[n]} are already sorted. Give an algorithm to sort
the array A in O(n) time and O(1)space
有没有人可以指导一下?
c****p
发帖数: 6474
2
这题现在都成悬案了

[0

【在 I***A 的大作中提到】
: Given an array A of n elements and an integer k (where k: ]...A[k]}and {A[k+1]...A[n]} are already sorted. Give an algorithm to sort
: the array A in O(n) time and O(1)space
: 有没有人可以指导一下?

d*******l
发帖数: 338
3
这题的一个特例就是那个把a1 a2 ..an b1 b2 .. bn变成a1 b1 a2 b2 .. an bn的题。
那题要求inplace不是没人给出O(n)的办法么,这题的普遍情况应该复杂的多。
f*******t
发帖数: 7549
4
有可以算作O(n)的解法
http://www.mitbbs.com/article/JobHunting/31948939_0.html

【在 d*******l 的大作中提到】
: 这题的一个特例就是那个把a1 a2 ..an b1 b2 .. bn变成a1 b1 a2 b2 .. an bn的题。
: 那题要求inplace不是没人给出O(n)的办法么,这题的普遍情况应该复杂的多。

d*******l
发帖数: 338
5
看过那个解法,确实很巧妙。
不过那里面也说如果算上计算index应该不止O(n)。这题就更没规律了,或许没有O(n)
inplace的算法也说不定。

【在 f*******t 的大作中提到】
: 有可以算作O(n)的解法
: http://www.mitbbs.com/article/JobHunting/31948939_0.html

I***A
发帖数: 6
6
好像有篇论文是专门将这个问题的; 感觉这个问题有点难度;
b*****c
发帖数: 1103
7
这不就是in place merge sort????
http://blog.ibread.net/345/in-place-merge-sort/
1 (共1页)
进入JobHunting版参与讨论
相关主题
Groupon 電面请问这题是什么意思
请教一个常见的面试题的答案这题怎么做?
求一下这题解法。median of an array of ints, 请问这题的经典回答是什么?谢谢
终于弄明白median of two sorted arrays了,发帖庆祝一下请教一道L的题
一个小公司面经一个特别的inplace merge two sorted arrays
请教一道题目[算法] unsorted array
Google电话面试题目Search in a sorted, rotated list
A家面试题Given an array of N integers from range [0, N] and one is missing. Find the missing number.
相关话题的讨论汇总
话题: elements话题: array话题: give话题: given话题: sort