w******1
发帖数: 520 | 1 有1,2,....一直到n的无序数组，求排序算法，并且要求时间复杂度为O(n)，空间复杂
度O(1)，使用交换，而且一次只能交换两个数.（华为）
分析：数组的特点是值和下标满足一定的关系，以此作为交换的终止条件。
但这个算法的时间复杂度如何证明是O(n)呢？
#include
int main()
{
int a[] = {10,6,9,5,2,8,4,7,1,3};
int len = sizeof(a) / sizeof(int);
int temp;
for(int i = 0; i < len; )
{
if ( a[i] != i + 1)//下标和值不满足对应关系
{
temp = a[a[i] - 1]; //不相等的话就把a[i]交换到与索引相应的位置
a[a[i] - 1] = a[i];
a[i] = temp;
}
else
i++; // 保存，以后此值不会再动了
}
for (int j = 0; j < len; j++)
cout<
return 0;
} | w******1
发帖数: 520 | | d*******8
发帖数: 785 | 3 这个可以0（N）的，因为是1-n个数在n大数组里，
【在 w******1 的大作中提到】
: 有1,2,....一直到n的无序数组，求排序算法，并且要求时间复杂度为O(n)，空间复杂
: 度O(1)，使用交换，而且一次只能交换两个数.（华为）
: 分析：数组的特点是值和下标满足一定的关系，以此作为交换的终止条件。
: 但这个算法的时间复杂度如何证明是O(n)呢？
: #include
: int main()
: {
: int a[] = {10,6,9,5,2,8,4,7,1,3};
: int len = sizeof(a) / sizeof(int);
: int temp;
| m******9
发帖数: 968 | 4 既然是1到n的值域, 又放在大小为n的数组里, 把数组重新写一遍就可以,不需要排序吧 | d*******8
发帖数: 785 | 5 但是这个代码是错的，应该是交换直到 A[i] = i+1
void sort(int A[], int n)
{
for(int i=0;i
{
while(A[i]!= i+1 )
swap(A[i], A[A[i]-1]);
}
}
虽然是For循环里嵌套while,但是
因为每个数至多被Swap2次，所以是0（N）
【在 d*******8 的大作中提到】
: 这个可以0（N）的，因为是1-n个数在n大数组里，
| w******1
发帖数: 520 | 6 我带入值
当
i = 0 的时候， 这几个就做了好几次啊。
temp = a[a[i] - 1];
a[a[i] - 1] = a[i];
a[i] = temp; | d*******8
发帖数: 785 | 7 题目要求你只用Swap操作吧，没有赋值，呵呵
【在 m******9 的大作中提到】
: 既然是1到n的值域, 又放在大小为n的数组里, 把数组重新写一遍就可以,不需要排序吧
| B*****t
发帖数: 335 | 8 i每次增加1至少会排好一个数， i取值从0到n-1， 复杂度O(n)
【在 w******1 的大作中提到】
: 有1,2,....一直到n的无序数组，求排序算法，并且要求时间复杂度为O(n)，空间复杂
: 度O(1)，使用交换，而且一次只能交换两个数.（华为）
: 分析：数组的特点是值和下标满足一定的关系，以此作为交换的终止条件。
: 但这个算法的时间复杂度如何证明是O(n)呢？
: #include
: int main()
: {
: int a[] = {10,6,9,5,2,8,4,7,1,3};
: int len = sizeof(a) / sizeof(int);
: int temp;
| g*******y
发帖数: 1930 | 9 这个是对的
对1-n的in place O(n)是可以做到的，以前google有个面试题是停车场有1-N编号的N辆车乱序，1
个空位，要求sort好，跟这个题基本上是一样的。
【在 d*******8 的大作中提到】
: 但是这个代码是错的，应该是交换直到 A[i] = i+1
: void sort(int A[], int n)
: {
: for(int i=0;i: {
: while(A[i]!= i+1 )
: swap(A[i], A[A[i]-1]);
: }
: }
: 虽然是For循环里嵌套while,但是
| d*******8
发帖数: 785 | 10 赞小尾羊，我要烧香拜佛求狗狗问我我会的题目..
辆车乱序，1
【在 g*******y 的大作中提到】
: 这个是对的
: 对1-n的in place O(n)是可以做到的，以前google有个面试题是停车场有1-N编号的N辆车乱序，1
: 个空位，要求sort好，跟这个题基本上是一样的。
| | | m******9
发帖数: 968 | 11 其实这个题另外一个写法就是,将从头到尾swap的过程, 做2次就可以了:
比如:
这个题目另外2个变形就是: 找missing和duplicate | r****o
发帖数: 1950 | 12 这种sort是不是得要1-n全排满，且每个元素只有一个才行阿。
辆车乱序，1
【在 g*******y 的大作中提到】
: 这个是对的
: 对1-n的in place O(n)是可以做到的，以前google有个面试题是停车场有1-N编号的N辆车乱序，1
: 个空位，要求sort好，跟这个题基本上是一样的。
| r**u
发帖数: 1567 | 13 swap needs assign value, isn't it?
【在 d*******8 的大作中提到】
: 题目要求你只用Swap操作吧，没有赋值，呵呵
| c**********r
发帖数: 472 | 14 雷死了，这也叫题。。。。。。。。。
直接输出1到n。 | w******1
发帖数: 520 | 15 这个题目另外2个变形就是: 找missing和duplicate
在哪个地方加入这个判断呢？ | r****o
发帖数: 1950 | 16 还是没搞明白为什么要做2次啊。
【在 m******9 的大作中提到】
: 其实这个题另外一个写法就是,将从头到尾swap的过程, 做2次就可以了:
: 比如:
: 这个题目另外2个变形就是: 找missing和duplicate
| a********n
发帖数: 369 | 17 第一次把第一个数和下标为1的数交换，这样第一个数就对了，第二次把第二个数和下标为2的数交换，
排好第二个数，这样n次就能排好n个数吧~
PS: 你申请full time还是intern？~
【在 w******1 的大作中提到】
: 有1,2,....一直到n的无序数组，求排序算法，并且要求时间复杂度为O(n)，空间复杂
: 度O(1)，使用交换，而且一次只能交换两个数.（华为）
: 分析：数组的特点是值和下标满足一定的关系，以此作为交换的终止条件。
: 但这个算法的时间复杂度如何证明是O(n)呢？
: #include
: int main()
: {
: int a[] = {10,6,9,5,2,8,4,7,1,3};
: int len = sizeof(a) / sizeof(int);
: int temp;
| w******1
发帖数: 520 | 18 这个不是面试遇到的题，
是在网上看到的题目。
下标为2的数交换，
【在 a********n 的大作中提到】
: 第一次把第一个数和下标为1的数交换，这样第一个数就对了，第二次把第二个数和下标为2的数交换，
: 排好第二个数，这样n次就能排好n个数吧~
: PS: 你申请full time还是intern？~
| r****o
发帖数: 1950 | 19 请问，为什么这个从头到尾做2遍swap就可以了呢?
【在 m******9 的大作中提到】
: 其实这个题另外一个写法就是,将从头到尾swap的过程, 做2次就可以了:
: 比如:
: 这个题目另外2个变形就是: 找missing和duplicate
| b******v
发帖数: 1493 | 20 已经知道是1,2,...,n那么直接写入a[0]=1, a[1]=2, ..., a[n-1]=n不就行了吗？
【在 w******1 的大作中提到】
: 有1,2,....一直到n的无序数组，求排序算法，并且要求时间复杂度为O(n)，空间复杂
: 度O(1)，使用交换，而且一次只能交换两个数.（华为）
: 分析：数组的特点是值和下标满足一定的关系，以此作为交换的终止条件。
: 但这个算法的时间复杂度如何证明是O(n)呢？
: #include
: int main()
: {
: int a[] = {10,6,9,5,2,8,4,7,1,3};
: int len = sizeof(a) / sizeof(int);
: int temp;
| | | d**e
发帖数: 6098 | 21 不明为什么swap两次？
就lz的例子 10,6,9,5,2,8,4,7,1,3
i = 0时，while就不止两次
【在 d*******8 的大作中提到】
: 但是这个代码是错的，应该是交换直到 A[i] = i+1
: void sort(int A[], int n)
: {
: for(int i=0;i: {
: while(A[i]!= i+1 )
: swap(A[i], A[A[i]-1]);
: }
: }
: 虽然是For循环里嵌套while,但是
| r****o
发帖数: 1950 | 22 请问这两个找missing和duplicate的变形具体是怎么回事，多谢。
【在 m******9 的大作中提到】
: 其实这个题另外一个写法就是,将从头到尾swap的过程, 做2次就可以了:
: 比如:
: 这个题目另外2个变形就是: 找missing和duplicate
| z*********h
发帖数: 133 | 23 For missing和duplicate,just calculate the sum
【在 r****o 的大作中提到】
: 请问这两个找missing和duplicate的变形具体是怎么回事，多谢。
| k***e
发帖数: 556 | 24 you may have satellite data
【在 b******v 的大作中提到】
: 已经知道是1,2,...,n那么直接写入a[0]=1, a[1]=2, ..., a[n-1]=n不就行了吗？
| r****o
发帖数: 1950 | 25 what is satellite data?
【在 k***e 的大作中提到】
: you may have satellite data
| s********f
发帖数: 510 | 26 重写一遍需要O(N)的space,这里规定了只能用交换
既然是1到n的值域, 又放在大小为n的数组里, 把数组重新写一遍就可以,不需要排序吧
【在 m******9 的大作中提到】
: 既然是1到n的值域, 又放在大小为n的数组里, 把数组重新写一遍就可以,不需要排序吧
| s******9
发帖数: 84 | 27 赞！
【在 c**********r 的大作中提到】
: 雷死了，这也叫题。。。。。。。。。
: 直接输出1到n。
|
|
