p*****2 发帖数: 21240 | 1 一个整数数组。现在要求找两个value不同的元素swap,使得结果数组是非排序的。
需要O(n)的复杂度 |
l*********8 发帖数: 4642 | 2 结果是“非排序”的?
【在 p*****2 的大作中提到】 : 一个整数数组。现在要求找两个value不同的元素swap,使得结果数组是非排序的。 : 需要O(n)的复杂度
|
p*****2 发帖数: 21240 | 3
嗯。要是排序的就神奇了。
【在 l*********8 的大作中提到】 : 结果是“非排序”的?
|
l*********8 发帖数: 4642 | 4 假如本来就是无序的数组呢? 还需要swap吗?
【在 p*****2 的大作中提到】 : : 嗯。要是排序的就神奇了。
|
l*****a 发帖数: 14598 | 5 这种不明出处的无力头的题旧不要讨论了
【在 l*********8 的大作中提到】 : 假如本来就是无序的数组呢? 还需要swap吗?
|
l*********8 发帖数: 4642 | 6 well, 我已经写了一个。。
bool swapToUnsort(int [] A,int length)
{
for (int i=1; i
if (A[i] > A[i-1]) {
swap(A[i], A[i-1]);
return true;
}
if (A[i] < A[i-1] && i+1 < length) {
swap(A[i], A[i+1]);
return true;
}
}
return false;
}
【在 l*****a 的大作中提到】 : 这种不明出处的无力头的题旧不要讨论了
|
l*****a 发帖数: 14598 | 7 7 7 6
另外需要找value不同的swap
【在 l*********8 的大作中提到】 : well, 我已经写了一个。。 : bool swapToUnsort(int [] A,int length) : { : for (int i=1; i: if (A[i] > A[i-1]) { : swap(A[i], A[i-1]); : return true; : } : if (A[i] < A[i-1] && i+1 < length) { : swap(A[i], A[i+1]);
|
p*****2 发帖数: 21240 | 8
需要。必须要swap一次。
【在 l*********8 的大作中提到】 : 假如本来就是无序的数组呢? 还需要swap吗?
|
l*********8 发帖数: 4642 | 9 good catch!
【在 l*****a 的大作中提到】 : 7 7 6 : 另外需要找value不同的swap
|
l*********8 发帖数: 4642 | 10 如果必须要swap一次,而且swap的两个values不同的话, 还是挺容易写错的一道题目
。
【在 p*****2 的大作中提到】 : : 需要。必须要swap一次。
|
|
|
p*****2 发帖数: 21240 | 11
是。挺tricky的。
【在 l*********8 的大作中提到】 : 如果必须要swap一次,而且swap的两个values不同的话, 还是挺容易写错的一道题目 : 。
|
p*****2 发帖数: 21240 | 12
可以扩展一下思路。
【在 l*****a 的大作中提到】 : 这种不明出处的无力头的题旧不要讨论了
|
l*********8 发帖数: 4642 | 13 挺tricky的,写错了好几次
bool swapToUnsort(int [] A,int length)
{
if ( (length >= 2 && A[0] < A[1] )
|| (length >= 3 && A[0] > A[2] ) {
swap(A[0], A[1])
return true;
}
for (int i=2; i
if (A[i] != A[i-1]) {
swap(A[i], A[i-1]);
return true;
}
}
return false;
}
【在 p*****2 的大作中提到】 : : 可以扩展一下思路。
|
p*****2 发帖数: 21240 | 14
how about [2, 3, 1]?
【在 l*********8 的大作中提到】 : 挺tricky的,写错了好几次 : bool swapToUnsort(int [] A,int length) : { : if ( (length >= 2 && A[0] < A[1] ) : || (length >= 3 && A[0] > A[2] ) { : swap(A[0], A[1]) : return true; : } : for (int i=2; i: if (A[i] != A[i-1]) {
|
l*********8 发帖数: 4642 | 15 (length >= 3 && A[0] > A[2] )
swap(A[0], A[1])
结果是 [3, 2, 1]; 这里的sorted是指升序的, [3,2,1]算无序的。
【在 p*****2 的大作中提到】 : : how about [2, 3, 1]?
|
p*****2 发帖数: 21240 | 16
3 2 1 也是有序呀。
【在 l*********8 的大作中提到】 : (length >= 3 && A[0] > A[2] ) : swap(A[0], A[1]) : 结果是 [3, 2, 1]; 这里的sorted是指升序的, [3,2,1]算无序的。
|
l*********8 发帖数: 4642 | 17 这个看怎么定义了。我觉得算逆序。
如果用缺省的 std:is_sorted 来测的话,结果是 false.
【在 p*****2 的大作中提到】 : : 3 2 1 也是有序呀。
|
p*****2 发帖数: 21240 | 18
查了一下,说的很清楚这个api只能查升序。
Checks if the elements in range [first, last) are sorted in ascending order.
【在 l*********8 的大作中提到】 : 这个看怎么定义了。我觉得算逆序。 : 如果用缺省的 std:is_sorted 来测的话,结果是 false.
|
l*********8 发帖数: 4642 | 19 用comp 参数把降序定义成“升序”,就可以检查降序了。
order.
【在 p*****2 的大作中提到】 : : 查了一下,说的很清楚这个api只能查升序。 : Checks if the elements in range [first, last) are sorted in ascending order.
|
c********t 发帖数: 5706 | 20 哪里的题?
【在 p*****2 的大作中提到】 : 一个整数数组。现在要求找两个value不同的元素swap,使得结果数组是非排序的。 : 需要O(n)的复杂度
|
p*****2 发帖数: 21240 | 21
竞赛题。
【在 c********t 的大作中提到】 : 哪里的题?
|