Chinaunix首页 | 论坛 | 博客
  • 博客访问: 536905
  • 博文数量: 45
  • 博客积分: 931
  • 博客等级: 准尉
  • 技术积分: 590
  • 用 户 组: 普通用户
  • 注册时间: 2005-04-17 13:27
文章分类

全部博文(45)

文章存档

2013年(6)

2012年(15)

2011年(23)

2005年(1)

分类: C/C++

2012-09-02 14:12:56

问题:

一个int数组, 比如 array[],里面数据无任何限制,要求求出 所有这样的数array[i],其左边的数都小于等于它,右边的数都大于等于它。能否只用一个额外数组和少量其它空间实现。

分析:
这题很直观的一个算法是,挨个的查找各个元素是否满足条件,算法的复杂度是O(n^2),太过复杂。

但如果我们在从左到右扫描数组的时候,能够维护一个candidate的数组, 该数组的元素满足: 到目前为止,这些元素都大于等于它前面的元素,而小于等于到目前为止扫描到的它右边的所有元素。 容易证明, candidate数组中的元素是按照非递减顺序排列的,即对任意的i
当我们扫描到一个小的元素的时候,需要从右到左(从大到小)的判断cand数组中的元素是否还满足条件,知道找到第一个不大于当前扫面元素的cand.

下面是算法的实现:

点击(此处)折叠或打开

  1. int findNum(int *arr, int n)
  2. {
  3.     if(arr == NULL) return 0;
  4.     int *cand = new int[n];
  5.     int idx = 0; //记录当前cand数组中的元素个数。
  6.     cand[idx++] = arr[0];
  7.     int max = arr[0], i;
  8.     for(i=1; i<n; i++) {
  9.         if( arr[i] >= max) {
  10.             cand[idx++] = arr[i];
  11.             max = arr[i];
  12.         } else {
  13.             while(idx > 0 && cand[idx-1] > arr[i]) idx--;
  14.         }
  15.     }
  16.     printf(" num: ");
  17.     for(i=0; i<idx; i++) printf("%d ", cand[i]);
  18.     printf("\n");
  19.     return idx;
  20. }
  21. void testFindNum()
  22. {
  23.     //int arr[20] = {3, 1, 6, 4, 5, 7, 9, 8, 10, 14, 12};
  24.     int arr[20] = {1, 2, 4, 5, 6, 7, 8, 9, 10, 3, 11};
  25.     int count = 0;
  26.     count = findNum(arr, 11);
  27. }

整个算法只需要对原来的数组扫描一次, 并且每个元素进入或者退出candidate数组最多一次。 算法在最坏情况下最多进行比较2*n次,时间和空间复杂度都是O(n).

阅读(5281) | 评论(1) | 转发(0) |
给主人留下些什么吧!~~

最大行业软件2012-11-03 14:41:33

ISOGRAPH_AVSIM_V10.0

ADINA系列产品:
ADINA.V8.8.1

CROCODILE.TECHNOLOGY.V609  系统控制仿真软件

Esteco.modeFRONTiER.v4.3.0 20101110 优化设计

ETA系列:
ETA.CAD.Translator.v1.200704
ETA.VPG.v3.3 汽车整车仿真软件
ETA_DYNAFORM_V5.6(多语言版,包括中文)
(DYNAFORM 是ETA开发的用于板料成形模拟的软件包。针对板料冲压的工艺特点,开发了方便高效的前后处理器,极大地缩短

了模型准备的周期。求解器采用LS-DYNA,基于增量法有限元理论,分析结果准确可靠。DYNAFORM可以模拟预压边、拉延、翻

边、弯曲、多工步成形等工艺过程,能够预测板料起皱、拉裂、回