[半zz]迅雷笔试题

[半zz]迅雷笔试题

1 /////////////////////////////////////////////////

2 //迅雷笔试题:

3//有N个大小不等的自然数(1–N),请将它们由小到大排序。

4//要求程序算法:时间复杂度为O(n),空间复杂度为O(1)。

10#include <iostream>

11using namespace std;

12int sort(int data[],int n);

13int main()

14{

15 int data[] = {8,7,9,4,6,5,3,2,1};

16 for(int i = 0 ;i < sizeof(data)/sizeof(int);i++)

17 cout<<data[i]<<“ “;

18 cout<<endl;

19 sort(data,sizeof(data)/sizeof(int));

20 system(“pause“);

21 return 1;

22}

23int sort(int data[],int n)

24{

25 //保证空间复杂度为O(1)

26 int tmp = 0;

27 for(int i = 0;i < n;i++)

28 {

29 //移动,直到第data[i]为i+1的时,while结束循环。向后继续判断

30 while(data[i] != i+1)

31 {

32 //每次循环保证了data[i-1]的正确。总共有n个所以时间复杂度为O(N)

33 tmp = data[data[i]–1];

34 data[data[i]–1] = data[i];

35 data[i] = tmp;

36 }

37 }

38 for(int i = 0;i < n;i++)

39 cout<<data[i]<<“ “;

40 cout<<endl;

41 return 1;

42}

看了这题,我也花了些时间想了想,结果想出来的代码和这家伙的有些不一样,

我想不能让我白想啊,所以把自己的代码也贴上来,嘿嘿。。。。

for(int i = 0;i < n;)

{

//移动,直到第data[i]为i+1的时,while结束循环。向后继续判断

// while(data[i] != i+1)

// {

// //每次循环保证了data[i-1]的正确。总共有n个所以时间复杂度为O(N)

// tmp = data[data[i]-1];

// data[data[i]-1] = data[i];

// data[i] = tmp;

// }

if (data[i] != i+1)

{

tmp = data[data[i]-1];

data[data[i]-1] = data[i];

data[i] = tmp;

}

else i++;

}

思想是一样的,我感得还是我的好理解些,起码我只用了一重循环 ;D

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏个人随笔

ADO.NET查询和操作数据库

stringbuilder 类 stringbuilder类:用来定义可变字符串 stringbulider Append(string value)   在结...

3365
来自专栏恰同学骚年

Hadoop学习笔记—11.MapReduce中的排序和分组

  从上图中可以清楚地看出,在Step1.4也就是第四步中,需要对不同分区中的数据进行排序和分组,默认情况下,是按照key进行排序和分组。

1102
来自专栏分布式系统进阶

Librdkafka的基础数据结构 1 --- 队列

两个元素: tqh_first: 指向队列的第一个成员; tqh_last: 存的是队列里的最后一个元素的 next指针的变量地址, 这个二级指针太有用了,...

952
来自专栏java一日一条

Java中的语法糖

语法糖方便了程序员的开发,提高了开发效率,提升了语法的严谨也减少了编码出错误的几率。我们不仅仅在平时的编码中依赖语法糖,更要看清语法糖背后程序代码的真实结构,这...

612
来自专栏书山有路勤为径

二分查找

已知一个排序数组A,如A= [-1,2,5,20,90,100,207,800] 另外一个乱序数组B,如B =[50,90,3,-1,207,80] 求B中...

864
来自专栏IT可乐

深入理解计算机系统(2.3)------布尔代数以及C语言运算符

  本篇博客我们主要讲解计算机中的布尔代数以及C语言的几个运算符。 1、布尔代数   我们知道二进制值是计算机编码、存储和操作信息的核心,随着计算机的发展,围绕...

2295
来自专栏老马说编程

(27) 剖析包装类 (中) / 计算机程序的思维逻辑

本节继续探讨包装类,主要介绍Integer类,下节介绍Character类,Long与Integer类似,就不再单独介绍了,其他类基本已经介绍完了,不再赘述。 ...

22210
来自专栏java学习

面试题21(关于&、&&和|、||的用法)+

根据下面的代码,String s = null;会抛出NullPointerException异常()? A if( (s!=null) & (s.length...

3488
来自专栏阮一峰的网络日志

Base64笔记

昨天的《MIME笔记》中提到,MIME主要使用两种编码转换方式----Quoted-printable和Base64----将8位的非英语字符转化为7位的ASC...

1684
来自专栏开发与安全

实现一些字符串操作标准库函数、解决一些字符串问题

一、实现字符串操作标准库函数 (1)、strcpy、strncpy、memmove、memcpy、memset、strlen、strncat 的实现 C++ C...

3159

扫码关注云+社区

领取腾讯云代金券