关于一道1到N自然数排序的华为面试题的疑问

Question

本帖最后由 zhenge1020 于 2010-09-10 16:55:15 编辑

Answer 1

有N个大小不等的自然数（1--N），请将它们由小到大排序。   
要求程序算法：时间复杂度为O(n)，空间复杂度为O(1)。创建一个大小为N的数组，直接按下标放到数组就可以了。int[] srcNs = {1, 3, 2, 5, ....., N, ...., X}; // 你的那N个自然数
int[] ns = new int[N]; for (int i = 0; i < N; ++i) {
    ns[srcNs[i] - 1] = srcNs[i];
}收功。

Answer 2

for (int i = 0; i < arr.length; i++) {
while (arr[i] != i + 1) {
temp = arr[i];
arr[i] = arr[arr[i] - 1];
arr[temp - 1] = temp;
}
}
}这个算法就是一直换到当前位置上的元素就是它的需要的值，然后才换下一个。
在很坏的情况下，时间复杂度是O(n * n)

Answer 3

恩，但是网上那个有cdn++的那种方式不就比我多了这个参数么？为什么复杂度就是n了？有点不明白

Answer 4

这个cdn++是用来记录交换次数的，跟复杂度没关系。
可能他以为，交换了N次，复杂度就是N吧。

Answer 5

呵呵，不喜欢这种命名方式，连个count都要简写，应该是受微软的风格影响。

Answer 6

你的意思是他理解的或许也可能有点问题？要是说交换算一次复杂度，他这样认为交换n次复杂度是n的haunted，其实选择排序也是可以这样实现的，最多只交换n次，但是比较的次数是在n^2的数量级的

Answer 7

我只是引用网上的别人发的实现算法，偶还真不知道是count缩写 呵呵

Answer 8

cnt就是起到一个计数的作用，计算交换了多少次，完全可以不要

Answer 9

void sort(int arr[], int n)
{
 int i;
 int t; /*临时变量：空间复杂度O(1)*/
 for (i=0; i<n; i++) /*时间复杂度O(n)*/
 {
  t = arr[arr[i]]; /*下标为arr[i]的元素，排序后其值就是arr[i]*/
  arr[arr[i]] = arr[i];
  arr[i] = t;
 }
} 我觉得，其实答案是不是应该是这个

Answer 10

这么说直接 for(int i=0;i<n;i++){System.out.println(i)};不是更方便

Answer 11

网上的那个是不是会越界啊，只有0到(n-1)的下标啊，当他运行到i=n时，arr[i]不报错么楼主的应该考虑到这个问题了（没仔细看），不过思路都是一个，其实只要思路没问题，多调试几遍就知道结果了~

Answer 12

这样不行的..要确保i存到a[i]以后，才能i++;
lz贴的两段代码是同一个算法，都ok啊. 不过第一个的数组下标溢出了，要-1....

Answer 13

汗，自己也没注意哦，是i放到a[i-1]以后，才能i++;

Answer 14

就是1-N的自然数.而且如果仅仅是整数排序，那还是什么排序算法吗?int数值传递直接赋值就可以了int[] a=new int[n];
for(int i=1;i<=n;i++){
a[i]=i;
}
数组a就是结果

Answer 15

使用TreeSet数据结构呢?
Set<Integer> numberSet=new TreeSet<Integer>(new Comparator(){
public int compare(Integer o1, Integer o2)
{
     return o1.compareTo(o2);
}
});
for(int i:arr)
   numberSet.add(i);
时间复杂度为o(n),空间复杂读为o(1);

Answer 16

http://blog.csdn.net/hongyuan19/archive/2007/11/16/1887656.aspx刚刚看到- -~一起看看吧,,,

Answer 17

N 个大小不等的 1-N 的数？
那不管参数数组啥样，直接在里边给参数数组各元素赋值可以不void sort(int arr[], int n){
for (int i = 0; i < arr.length; i++) {
arr[i] = i + 1;
}
}

Answer 18

是已经给你了1到n的自然数，无序的，要排成个有序ide，你这样叫赋值啊

Answer 19

你的代码和例子给出的是一样的。我也明白你说的问题
只是我觉得这个参数的特殊性让人都只是必然是 1-n 的连续数列
为什么要换了换去的调整参数数组中的各个数字的位置
严格说来 for 循环也是占用空间的 为 i 开的空间就是 1 怎么不算到条件里去呢

Answer 20

普通的排序算法:
double[] a=new double[]{3.4,5.3,....}
for(int i=1,len=a.length;i<len;i++){
int the=a[i];
int j=i;
do{
int help=a[j-1];
if(help<the)
a[j]=help;
else
break;
}while(--j>0);
a[j]=the;
}

Answer 21

我觉得 O(n) 只是说线性的，不一定是说它跟 n 相等吧。加一个 for 循环的变量 i 是个常量，就是 O(1)，随数组长度呈线性变化的就是 O(n)的。

Answer 22

如果已经知道是1 - N, 那还排什么序? 直接填写1 - N不就行了.

for (int i = 0; i < array.length; i++)
{
is[i] = i;
}

Answer 23

这种方式行么？
Set 是无序的吧

Answer 24

 for (int i = 1; i <= n; i++){  while(arr[i] != i){ // 这个循环总共最多执行n次  t = arr[arr[i]];  arr[arr[i]] = arr[i];  arr[i] = t;  ++cnt;  } }后来看了下，这个算法没有错，时间复杂度是O(2 * n)，即O(n)，

Answer 25

我又写了个JAVA的算法,与LZ的算法一样,复杂就是O(2n).main里有生成乱序的方法
import java.util.Arrays;
import java.util.Random;/**
 * 有N个大小不等的自然数（1--N），请将它们由小到大排序。 要求程序算法：时间复杂度为O(n)，空间复杂度为O(1)。
 * 
 * @author chouy
 */
public class SortArrayFrom1toN extends Base
{
public static int N = 5000;
public static Random random = new Random(); public static void main(String[] args)
{
int[] is = new int[N];
for (int i = 0; i < is.length; i++)
{
is[i] = i;
}
// 打乱顺序
int tmp;
for (int i = 0; i < is.length; i++)
{
int j = random.nextInt(N);
tmp = is[i];
is[i] = is[j];
is[j] = tmp;
}
info(Arrays.toString(is));
info(Arrays.toString(new SortArrayFrom1toN().sort(is)));
} /**
 * 用交换的方法进行排序.<br>
 * 交换方法:交换回来的数如果不应该在当前位置,则再把它与它应该在的位置交换
 * 
 * @param array
 * @return
 */
public int[] sort(int[] array)
{
int exchangeTimes = 0; // 比较计数器
int tmp;
for (int i = 0; i < array.length; i++)
{
if (array[i] != i)
{
tmp = array[array[i]];
array[array[i]] = array[i];
array[i] = tmp;
i--;
exchangeTimes++;
}
}
debug("exchangeTimes = " + exchangeTimes);
return array;
}
}

Answer 26

楼上兄台的代码好像是死循环？
在sort方法中 for (int i = 0; i < array.length; i++)
然后i--
另外数组有点越界，帮你改进一下：
public static int[] sort(int[] array)
    {
        int exchangeTimes = 0; // 比较计数器
        int tmp;
        for (int i = 0; i < array.length; i++)
        {
            if (array[i] != i)
            {
                tmp = array[array[i]-1];
                array[array[i]-1] = array[i];
                array[i] = tmp;
                i--;
                exchangeTimes++;
            }
        }
        return array;
    }
我测试的是int [] testInt=new int[]{5,3,1,4,2};
是死循环

Answer 27

这样才有点意义吧，否则用得着排序吗？
        private interface ISort { public int sort { get; } }
        private static void sort<valueType>(valueType[] values) where valueType : ISort
        {
            valueType value, nextValue;
            for (int nextIndex, index = values.Length - 1; index > 0; index--)
            {
                if ((nextIndex = (value = values[index]).sort - 1) != index)
                {
                    do
                    {
                        nextValue = values[nextIndex];
                        values[nextIndex] = value;
                    }
                    while ((nextIndex = (value = nextValue).sort - 1) != index);
                    values[index] = value;
                }
            }
        }

Answer 28

n就是让你统计执行次数，没换一次就少执行一次了，时间是O(n)

Answer 29

刚才想说的是cnt这个变量的作用，用来统计

Answer 30

// sort src[0...n], 1--N
int i; 
int temp;  // 空间复杂度: O(1)
for (i=0; i<N; i++)
{
    temp = src[src[i]-1]; 
    src[src[i]-1] = src[i]; 
    src[i] = temp; 
}

Answer 31

个人认为cnt只是计数，用来证明时间复杂度为O(n)

Answer 32

不是吧，N个元素，1-N，还互不相等，那不就是1，2，3，N么？
还排序干嘛：
int orignalArray={1,5,265,....};
for(int i=0;i<orignalArray.lengh;i++){
 orignalArray[i]=i+1;
}
这个题目是不是脑筋急转弯啊？

Answer 33

这个计数只能证明内层循环循环了多少次吧，
int[] array = new int[] { 6, 1, 7, 3, 4, 5, 2 };
大家试试这个需要交换6次的哦
外层循环又是n，所以还是相当于n^2的

Answer 34

int a[] = { 3,6,7,1,2,4,5};
void sort(int arr[])
{
int idx = 0;
int i = 0;
while(true)
{ if(a[i] == a[a[i] - 1])
i ++ ; if(i > 6)
break; idx = a[a[i] - 1] ;
a[a[i] - 1 ] = a[i];
a[i] = idx;  }
}
int _tmain(int argc, _TCHAR* argv[])
{ sort(a);
return 0;
}

Answer 35

有N个大小不等的自然数（1--N），请将它们由小到大排序。
这还用排？？？
N个，大小不等，自然数，那不就是1，2，3，4，5，6，7，N。脑残题目阿

Answer 36

楼主,不要纠结在必须要某某算法来排序上了,实际上:
"有N个大小不等的自然数（1--N），请将它们由小到大排序。 "已经很明确的告诉你了,1->N,N个大小不等的自然数,必定就是连续的,直接输出就是排序(这题目出的相当舒服,如果弄个0->N,你还需要判断中途可能缺失的自然数)

Answer 37

sort(int a[],int n)
{
  for(int i=0;i<n;i++){
     a[i]=i+1;
  }
}
既然确定了是一个包含1~N元素的数组。没有必要那么麻烦！直接给传进来的数组重新赋值就可以了！
问题不能一味的用同样的套路完成！往往简单的算法就是另外的思路！换个想法就很简单了！例如：就像只有0,1的矩阵一样，如果用二进制的方法不但简单，而且速度比你实在的访问二位数组快得多！

Answer 38

没有过java，用C写一个看看吧void sort(int arr[], int n)
{
  int i, j;
  
  for(i=0; i<n; i++)
  {
     j=arr[i];
     arr[i]=j-1;
     arr[j-1]=j;
  }
}说明：时间复杂度为o(n),空间复杂度为0(1)(定义了变量j，循环变量i不计)

Answer 39

对不起，写错了！
没用过java，用C写一个看看吧void sort(int arr[], int n)
{
  int i, j;
   
  for(i=0; i<n; i++)
  {
  j=arr[i];
  arr[i]=arr[j-1];
  arr[j-1]=j;
  }
}说明：时间复杂度为o(n),空间复杂度为0(1)(定义了变量j，循环变量i不计)

Answer 40

谢谢85楼的，不过貌似这种方式不行。单从循环应该是实现不了的。
测试代码：
public class OnSort {
public static void main(String[] args) {
int[] array = new int[] { 6, 1, 7, 3, 4, 5, 2 };
sort(array, array.length);
for(int i=0;i<array.length;i++){
System.out.print(array[i]+" ");
}
} static void sort(int arr[], int n) {
int i, j;
for (i = 0; i < n; i++) {
j = arr[i];
arr[i] = j - 1;
arr[j - 1] = j;
}
}
}
输出结果：
1 0 3 4 3 6 7 

Answer 41

用int[] array = new int[] { 6, 1, 7, 3, 4, 5, 2 };测试，测试结果：
1 5 3 4 2 6 7 

Answer 42

桶排序我也有看过，但是最坏的情况也是n^2 时间复杂度。下面这个网页有讲解
http://www.bsgz.net/Article/Class20/Class88/sjjg/200609/940.html

Answer 43

重新看了下题目，不用什么排序算法，直接输出就是了。华为出的什么题目？“有N个大小不等的自然数（1--N），请将它们由小到大排序。”  1～N只有N个自然数，还是大小不等的，那不就是1，2，3，4，5...N这题是脑筋急转弯？？？

Answer 44

那个分析只是说，当箱子太多而n少时，算下来就和n^2一样了。但实际上这个排序是线性的。
另外，华为这题直接一个for循环输出1～N就是了，不用管输入的是怎样的序列。