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 | |
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 | |
n****r
发帖数: 120 | |
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
: 是我理解错方法了吗
|
|
|
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吗？
|
|
|
h***i
发帖数: 1970 | |
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 |
