专栏首页轻扬小栈[半zz]迅雷笔试题

[半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 条评论
登录 后参与评论

相关文章

  • 百度网盘的php客户端 bpcs_uploader

    用户1130771
  • 从官方安装更新 openwrt for pogoplug 第二部分

    用户1130771
  • svn如此好的软件,竟现在才发现

    用户1130771
  • WordPress发布/更新文章、提交/审核评论自动清理VeryCloud缓存

    上一篇文章分享了WordPress 发布文章评论自动刷新腾讯云 CDN 的教程,而博客现在还用到了 VeryCloud 的 CDN,正好有朋友在文章后面留言说 ...

    张戈
  • Python中时间格式数据的处理

    1、时间转换 时间转换是指字符型的时间格式数据,转换成为时间型数据的过程。 一般从csv导入过来的文件,时间都保存为字符型格式的,需要转换。 时间转换函数: d...

    Erin
  • 使用 Python 实现几种常见的排序算法

    冒泡排序是最为基础的排序算法,其核心思想就是相邻元素两两比较,把较大的元素放到后面,在一轮比较完成之后,最大的元素就位于最后一个位置了,就好像是气泡,慢慢的浮出...

    周萝卜
  • 讲讲切比雪夫定理

    前面讲了大数定理,讲了中心极限定理,有读者留言让讲讲切比雪夫定理,安排。这一篇就来讲讲切比雪夫定理。

    张俊红
  • C++ string实现

    作为C++从业者,我相信都会被考察过实现简单的string类,包括构造、析构、拷贝构造以及赋值拷贝等,因为这能够很好的考察面试者的C++基本功。借看《剑指off...

    evenleo
  • 单基因生信分析流程(3)一文解决生存分析和临床参数相关分析

    用户1359560
  • pandas的一些小知识

    生信编程日常

扫码关注云+社区

领取腾讯云代金券