由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 刚做了一道有些怪异的题
相关主题
请问可以用二分法判断一个数组是否sorted吗?有没有这样的题型
找第K个最小的元素问道题的解题思路
有谁还记得这道题?这是道什么题?难题还是超级简单题?
BB家面经问一道面试题
一道msft的题感恩发面经-Amazon第一轮电面
有A[i]问题:Find the minimum number of "swaps" needed to sort an array
问个算法题,修改版A家杯具,面经
数组中找和为0的3个数,4个数问个题目,找不在区间内的所有数
相关话题的讨论汇总
话题: length话题: swap话题: int话题: return话题: true
进入JobHunting版参与讨论
1 (共1页)
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一次。

相关主题
有A[i]有没有这样的题型
问个算法题,修改版问道题的解题思路
数组中找和为0的3个数,4个数这是道什么题?难题还是超级简单题?
进入JobHunting版参与讨论
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 的大作中提到】
: 哪里的题?
1 (共1页)
进入JobHunting版参与讨论
相关主题
问个题目,找不在区间内的所有数一道msft的题
请教G的一道题,觉得有点难……有A[i]
一道面试题的优化问个算法题,修改版
最近面试的一个问题数组中找和为0的3个数,4个数
请问可以用二分法判断一个数组是否sorted吗?有没有这样的题型
找第K个最小的元素问道题的解题思路
有谁还记得这道题?这是道什么题?难题还是超级简单题?
BB家面经问一道面试题
相关话题的讨论汇总
话题: length话题: swap话题: int话题: return话题: true