由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 问题:Find the minimum number of "swaps" needed to sort an array
相关主题
再论 mini # of swaps to sort array.问一个amazon的数组排序题
问道面试题One Amazon question
一个容易记忆的permutation算法问题
请教一道题目Quick Sort的partition问题
amazon 电面题array a1,a2,... ,an, b1,b2,..., bn
今天电面又被老印黑了。。。。一个找duplicate element in an array的问题
Find the Kth smallest element in 2 sorted问一道题, 不是很难, 但不知道最优解是什么
Interview Question问一道g电面题
相关话题的讨论汇总
话题: array话题: idxmin话题: find话题: swaps话题: swap
进入JobHunting版参与讨论
1 (共1页)
n****r
发帖数: 120
1
An operation "swap" means removing an element from the array and appending
it at the back of the same array. Find the minimum number of "swaps" needed
to sort that array.
Eg :- 3124
Output: 2 (3124->1243->1234)
b*****u
发帖数: 648
2
不用到队尾排序的数字是从1开始的最长有序数组,比如例子里的{1,2},其余数字都
要依次从队尾重新入列,所以是4-2=2
p*****2
发帖数: 21240
3
这题以前是我贴的吧?
r**h
发帖数: 1288
4
cycle sort?

needed

【在 n****r 的大作中提到】
: An operation "swap" means removing an element from the array and appending
: it at the back of the same array. Find the minimum number of "swaps" needed
: to sort that array.
: Eg :- 3124
: Output: 2 (3124->1243->1234)

h***i
发帖数: 1970
5
inversions and merge sort.

【在 r**h 的大作中提到】
: cycle sort?
:
: needed

f*******t
发帖数: 7549
p*****2
发帖数: 21240
7

记错了。怎么印象中在CF上做过呀

【在 f*******t 的大作中提到】
: http://www.mitbbs.com/article0/JobHunting/32294603_0.html
n****r
发帖数: 120
8
学习了!谢谢大神的帮助!
r**h
发帖数: 1288
9
要是输入是2 1 4 3的话,因为2在1前面,因此
if (array[index] == target)
当target=2时候永远不成立,从而使得minswap = 3,但解是minswap = 2
是我理解错方法了吗

【在 f*******t 的大作中提到】
: http://www.mitbbs.com/article0/JobHunting/32294603_0.html
d*********g
发帖数: 154
10

我也觉得这个算法不对~

【在 r**h 的大作中提到】
: 要是输入是2 1 4 3的话,因为2在1前面,因此
: if (array[index] == target)
: 当target=2时候永远不成立,从而使得minswap = 3,但解是minswap = 2
: 是我理解错方法了吗

相关主题
今天电面又被老印黑了。。。。问一个amazon的数组排序题
Find the Kth smallest element in 2 sortedOne Amazon question
Interview Question问题
进入JobHunting版参与讨论
z****p
发帖数: 18
11
I think backtou has already given the answer. Let me elaborate it:
-Naive approach: find the smallest element in the array, "swap" it to the
tail; then find the 2nd smallest element, "swap" it to the tail; ...
-Improvement, if the first K elements are already in an increasing order in
the original array, then in the naive approach, we can simply start with the
K+1-th smallest element
-So the minimal number of "swaps" is N-K, where K is the longest prefix of
the sorted array that are already in the right order (they don't have to be
consecutive in the original array--they only have to be in the right order).

needed

【在 n****r 的大作中提到】
: An operation "swap" means removing an element from the array and appending
: it at the back of the same array. Find the minimum number of "swaps" needed
: to sort that array.
: Eg :- 3124
: Output: 2 (3124->1243->1234)

f*******t
发帖数: 7549
12
怎样两次能swap成1 2 3 4?

【在 r**h 的大作中提到】
: 要是输入是2 1 4 3的话,因为2在1前面,因此
: if (array[index] == target)
: 当target=2时候永远不成立,从而使得minswap = 3,但解是minswap = 2
: 是我理解错方法了吗

r**h
发帖数: 1288
13
第一次交换12,第二次交换34?
2143 - 1243 - 1234

【在 f*******t 的大作中提到】
: 怎样两次能swap成1 2 3 4?
f*****e
发帖数: 2992
14
n-(length of maximum consecutively increasing sequence, i.e., 1,2,3,..,i)
for 3124, n = 4, maximum consecutively increasing sequence is 12
thus 4 - 2 =2
for 2134, n = 4, length =1
thus 4 - 1 = 3

needed

【在 n****r 的大作中提到】
: An operation "swap" means removing an element from the array and appending
: it at the back of the same array. Find the minimum number of "swaps" needed
: to sort that array.
: Eg :- 3124
: Output: 2 (3124->1243->1234)

f*****e
发帖数: 2992
15
只能加到末尾,

【在 r**h 的大作中提到】
: 第一次交换12,第二次交换34?
: 2143 - 1243 - 1234

c********t
发帖数: 5706
16
嗯,基本达成共识。
具体怎么解呢? 先排序并存到另一个array, 再比较原数组得出longest prefix?
time O(nlgn) space O(n)?

in
the
be
).

【在 z****p 的大作中提到】
: I think backtou has already given the answer. Let me elaborate it:
: -Naive approach: find the smallest element in the array, "swap" it to the
: tail; then find the 2nd smallest element, "swap" it to the tail; ...
: -Improvement, if the first K elements are already in an increasing order in
: the original array, then in the naive approach, we can simply start with the
: K+1-th smallest element
: -So the minimal number of "swaps" is N-K, where K is the longest prefix of
: the sorted array that are already in the right order (they don't have to be
: consecutive in the original array--they only have to be in the right order).
:

f*******t
发帖数: 7549
17
你想输出每次交换的index吗?

【在 c********t 的大作中提到】
: 嗯,基本达成共识。
: 具体怎么解呢? 先排序并存到另一个array, 再比较原数组得出longest prefix?
: time O(nlgn) space O(n)?
:
: in
: the
: be
: ).

A***o
发帖数: 358
18
May be I am wrong, consider the following ...
Let the unsorted array be V=a_0, a_1, ... a_k, ... a_m
assume min(V)=a_k
'swap' all a_i such that i Let V_1 = a_0 ... a_(k-1)
w.l.g., assume min(V_1) = a_l
Let V_2 = a_(k+1) ... a_m
w.l.g., assume min(V_2) = a_r
Now scan V_2, 'swap' an a_i (k+1<=i<=m), if
(i) a_i > a_r and i < r; OR
(ii)a_i > a_l
O(n) time, O(1) space? :)

【在 c********t 的大作中提到】
: 嗯,基本达成共识。
: 具体怎么解呢? 先排序并存到另一个array, 再比较原数组得出longest prefix?
: time O(nlgn) space O(n)?
:
: in
: the
: be
: ).

z****p
发帖数: 18
19
I guess this problem is not about algorithm. It asks for the number of min
swaps. It's more like a math problem. As long as we give N-K, our job is
done, and we don't have to implement any algorithm.
Think this problem in another way:
-There is a large graph, where each node is a permutation of the given list
of data; there is an edge points from node i to node j if we can move from
permutation-i to permutation-j by using one "swap".
-Now the question is I pick two nodes i and k in the graph, where k is
special in that its permutation happens to be a sorted list; i is an
arbitrary node.
-Then I ask you "(1) What is length of the min-length path
from i to k in the graph (2) What are exact nodes on the path?"; however,
I didn't ask you to develop an algorithm to find that path, because doing
so may need a sorting first and then a backtrack of path--using that for the
purpose of sorting is not a good idea.

【在 c********t 的大作中提到】
: 嗯,基本达成共识。
: 具体怎么解呢? 先排序并存到另一个array, 再比较原数组得出longest prefix?
: time O(nlgn) space O(n)?
:
: in
: the
: be
: ).

c********t
发帖数: 5706
20
嗨!原来lz忘给原题的重要条件 数组是从 1-n的排列啊,搞得我一头雾水。

【在 f*******t 的大作中提到】
: 你想输出每次交换的index吗?
相关主题
Quick Sort的partition问题问一道题, 不是很难, 但不知道最优解是什么
array a1,a2,... ,an, b1,b2,..., bn问一道g电面题
一个找duplicate element in an array的问题Non-recursive permutation
进入JobHunting版参与讨论
h***i
发帖数: 1970
21
这个方法好,实现还简单

【在 f*******t 的大作中提到】
: http://www.mitbbs.com/article0/JobHunting/32294603_0.html
b*******e
发帖数: 217
22
starting from the first element to the last element:
if any element after it is smaller than it, swap this element to the enf of
the array
seems n^2 worst case.

needed

【在 n****r 的大作中提到】
: An operation "swap" means removing an element from the array and appending
: it at the back of the same array. Find the minimum number of "swaps" needed
: to sort that array.
: Eg :- 3124
: Output: 2 (3124->1243->1234)

b*******e
发帖数: 217
23
according to your algorithm for 2134, should be 4-2 = 2 since 34 is the
longest increasing substring.

【在 f*****e 的大作中提到】
: n-(length of maximum consecutively increasing sequence, i.e., 1,2,3,..,i)
: for 3124, n = 4, maximum consecutively increasing sequence is 12
: thus 4 - 2 =2
: for 2134, n = 4, length =1
: thus 4 - 1 = 3
:
: needed

g********r
发帖数: 58
24
不用 假定数组是1~n的某个排列
O(n) time + 常数 space 的解法 - 对吗?
int minSwap(int[] A) {
n = len(A)
idxMin = 0
valMin = A[idxMin]
for (int i = 0, i< n, i++)
if valMin > A[i]
valMin = A[i]
idxMin = i
if idxMin == n-1
return n-2
cnt = idxMin
leftMin = INT_MAX
for (int i = 0; i<= idxMin-1 ; i++)
if leftMin < A[i]
leftMin = A[i]
rightMin = A[n-1]
for (int i = n-1; i<= idxMin+1; i-- )
if A[i]> rightMin || A[i] > leftMin
cnt++
if A[i] < rightMin
rightMin = A[i]

return cnt
1 (共1页)
进入JobHunting版参与讨论
相关主题
问一道g电面题amazon 电面题
Non-recursive permutation今天电面又被老印黑了。。。。
Given a string, find all its permutations without any repetition?Find the Kth smallest element in 2 sorted
minMSwap 这题能比O(n^2)更快的解法吗Interview Question
再论 mini # of swaps to sort array.问一个amazon的数组排序题
问道面试题One Amazon question
一个容易记忆的permutation算法问题
请教一道题目Quick Sort的partition问题
相关话题的讨论汇总
话题: array话题: idxmin话题: find话题: swaps话题: swap