A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© long362144768 中级黑马   /  2013-9-25 10:30  /  1828 人查看  /  2 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 long362144768 于 2013-9-25 22:43 编辑

1,一个数组循环左移三位(数组长度大于10),求出最优的空间开销。

2 个回复

倒序浏览
本帖最后由 抽烟男孩 于 2013-9-25 22:23 编辑

这是一道考研体吧,好像用的是海豚算法。空间开销是O(1),跟具体是3
以下是关键代码:
  1. reverse(int[] arr,int from,int end){
  2. int temp;
  3. for(int i=from;i<from+(end - from)/2;i++){
  4. temp = arr[i];
  5. arr[i] = arr[end-i] ;
  6. arr[end-i]=temp;
  7. }
  8. }
  9. main(String[] args){
  10. int[] source ={};//要移动的数组
  11. reverse(source,0,source.length-4);
  12. reverse(source,source.length-3,soucer.lengtj-1);
  13. reverse(source,0,source.length-1);
  14. }
复制代码

评分

参与人数 1黑马币 +9 收起 理由
黄文伯 + 9

查看全部评分

回复 使用道具 举报
temp = arr[i];

arr[i] = arr[end-i] ;

arr[end-i]=temp;

这一部分可以优化,
     a[i]^=a[end-i];
     a[end-i]^=a[i];
     a[i]^=a[end-i];
所以空间开销为0.
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马