给定一个未经排序的数组,该数组中,有正数和负数,现在需要对它进行组合,使得组合后的数组负数在前,正数在后,并且要求保持原来的相对顺序。如:组合前:3,8,-4,100,-26,29组合后:-4,-26,3,8,100,29要求算法的时间复杂度为O(N),空间复杂度为O(1))。

2011-01-30 17:00:33

7 Answers

若你知道这些数的范围可用下面的算法

  
define(MAX_NUM,1000000); define(MIN_NUM,-1000000); //sort_array为要排序的数组,length为该数组长度 function NiuabilitySort($sort_array,$length) { //初始化基数组,预非配空间,与$sort_array大小无关 for ($i = MIN_NUM; $i < MAX_NUM; $i++) { $base_array[]=0; } for ($i = 0; $i< length; $i++) { if($sort_array[$i]<0){ $base_array[$sort_array[i]]++; }else{ $sort2_array[]=$sort_array[$i]; } } //更新排序结果到sort1_array中 int $j = 0; for ($i = MIN_NUM; $i < MAX_NUM; $i++) { if ($base_array[$i] != 0) { $len=cout($base_array[$i]); for ($k = 0; $k<$len;$k++){ $sort1_array[$j] = $i; $j++; } } } return array_merge ($sort1_array,$sort2_array); }

这个算法的思想是:在数字范围有限制的情况下,用一个数组(这里是base_array)记录要排序的数组中(sort1_array)每个数字出现的次数,然后再扫描一遍base_array数组,按次数去更新sort1_array,而更新值就是base_array当前的下标值。

base_array这个空间是常量,所以空间复杂度是O(1)。两次遍历,对sort1_array一遍扫描,时间复杂度是O(n),对base_array一遍扫描,时间复杂度是O(1),所以最后的时间复杂度是O(n)。

2011-01-30 20:21:37
  
$arr = array(3,8,-4,100,-26,29); $arr1 = array(); foreach($arr as $key => $val) { if($val >= 0 ) continue; unset($arr[$key]); array_push($arr1,$val); } $arr = array_merge($arr1,$arr);

取出负数将其push到一个新数组中,再将原值unset();最后两个数组合并。

2011-01-30 21:53:13
input[] = {1,7,-5,9,-12,15}; pts=&input[i]; pti=&input[i]; n=1; for(i=0;i<sizeof(input)-2;i++) { pts++; if (*(pts-1)<0) { (pts-2)->next = pts; (pts-1)->next = pti; } if(n && 0>*pti) pti++; else n=0; } if (0>input[sizeof(input)-1]) input[sizeof(input)-1]->next=pti;
2011-01-30 23:45:44

若是数组R中每个整数和数组R不太大的话可以用如下方法
设数组R大小为n m为使得10^m最接近n且大于n的整数
1.遍历一遍数组R对每个数做如下操作用记录该数应该处于哪个位置

int x=0,y=0;
for(int i=0;i<n;i++)
{

if(R[i]<0)
{
x++;
R[i]=R[i]*10^m+x;
}

else
{
y++;
R[i]=R[i]*10^m+y+x;
}

}

2.再遍历对每个数都放到其正确的位置

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

int w=R[i]%10^m;
int p=R[i]/10^m;
int Q=R[i];
int E;
while((i+1)!=w)
{
E=Q;
Q=R[w-1];
R[W-1]=E;
w=Q%10^m;
p=Q/10^m;
}
R[i]=p;

}
这样负数只被访问一遍 正数被访问两遍

2011-01-31 01:20:01

#include <stdio.h>
#include <string.h>

int main(int argc, char* argv[])
{
int a[] = {3, 8, 0, 0, -88, 1, 99, -5, -4, 100, 0, -26, 0, 0, 29};
int i, j, t;

////////////// 算法开始 ///////////////

// 找到第一个大于、等于0的数
for (i = 0; i < sizeof(a) / sizeof(a[0]); i++) {
if (a[i] >= 0) {
break;
}
}
for (j = i + 1; j < sizeof(a) / sizeof(a[0]); j++) {
if (a[j] <= 0) {
// 找到位置i后面的第一个小于、等于0的数
// 把这个数,移到第i个大于等于0的数前面
t = a[j];
memmove(&a[i + 1], &a[i], sizeof(a[0]) * (j - i));
a[i] = t;
if (t < 0) {
++i; // 由于插入了一个负数,第一个大于等于0的数的坐标后移一位
}
}
}

////////////// 算法结束 ///////////////

// 输出排序结果
for (i = 0; i < sizeof(a) / sizeof(a[0]); i++) {
printf("%d ", a[i]);
}
return 0;
}

// 说明
// 1) 算法虽然有两个循环,但是两个循环的时间复杂度之和是 O(n) 的。
// 2) 如果用于循环的变量 i,j 不算,就只有 t 用在数据交换,所以 空间复杂度 O(1)

2011-01-31 02:49:14

我有一种满足条件的算法,但是性能,我不敢说好
先说我的算法运用的存储策略,这个数组中,最大正数+1为MAX,最小负数-1为MIN,都初始化为0,遍历所有数组,得到MAX和MIN,如果其中有一个为0的话,那么算法结束,如果两个都有数,那么就这么来存储。正数+MAXn,永远都不会丢失正数本身,因为用这个数%MAX就可以,负数+MINn,永远都不会丢失负数本身,因为用这个数%MIN就可以,正数的个数为Z_NUM,负数个数为F_NUM这个在遍历的时候,也求出来
然后在下一次遍历的过程中,遇到第i的正数,正数=正数+MAX(F_NUM+i),遇到第j的负数,负数=负数+MINj其中F_NUM+i表示的是正数将会放到的索引处,j表示负数会放到的索引处
为了显示清楚,我就将数和索引分开,测试数据的数据为
数据 1,7,-5,9,-12,15
索引 2,3, 0,4, 1,5
最后遍历时,如果遍历时候的索引和本身要存放索引不一致,则交换
第一次交换后为
数据 -5,7, 1,9,-12,15
索引 0, 3, 2,4, 1,5
第二次交换后为
数据 -5,9, 1,7,-12,15
索引 0, 4, 2,3, 1,5
第三次交换后为(不用移位)
数据 -5,9, 1,7,-12,15
索引 0, 4, 2,3, 1,5
第4次交换后为(不用移位)
数据 -5,9, 1,7,-12,15
索引 0, 4, 2,3, 1,5
第5次交换后为
数据 -5,-12, 1,7, 9,15
索引 0, 1, 2,3, 4,5
......
同理,一直遍历结束,即可得到正确结果

2011-01-31 04:10:38
您不能回答该问题或者回答已经关闭!

相关文章推荐

  • C#实例解析适配器设计模式

    将一个类的接口变成客户端所期待的另一种接口,从而使原本因接口不匹配而无法在一起工作的两个类能够一起工作

  • C#中using指令的几种用法

    using + 命名空间名字,这样可以在程序中直接用命令空间中的类型,而不必指定类型的详细命名空间,类似于Java的import,这个功能也是最常用的,几乎每个cs的程序都会用到

  • C#协变和逆变

    “协变”是指能够使用与原始指定的派生类型相比,派生程度更大的类型,“逆变”则是指能够使用派生程度更小的类型

  • C#运行时相互关系

    C#运行时相互关系,包括运行时类型、对象、线程栈和托管堆之间的相互关系,静态方法、实例方法和虚方法的区别等等

  • 使用托管C++粘合C#和C++代码(二)

    本文实现一下C++代码调用C#代码的过程。我构造一个简单并且直观的例子:通过C++ UI 触发C# UI.

  • C#开发高性能Log Help类设计开发

    项目中要在操作数据库的异常处理中加入写Log日志,对于商业上有要求,写log时对其它操作尽可能影响小,不能因为加入log导致耗时太多

  • C#开发中的反射机制

    反射的定义:审查元数据并收集关于它的类型信息的能力。元数据(编译以后的最基本数据单元)就是一大堆的表,当编译程序集或者模块时,编译器会创建一个类定义表,一个字段定义表,和一个方法定义表等

  • Async和Await使异步编程更简单

    C#5.0中async和await两个关键字,这两个关键字简化了异步编程,之所以简化了,还是因为编译器给我们做了更多的工作

  • 使用托管C++粘合C#和C++代码(一)

    C#在xml读写,数据库操纵,界面构造等很多方面性能卓越;C++的效率高,是底层开发的必备武器

  • C#基础概念之延迟加载

    延迟加载(lazy load)是Hibernate3关联关系对象默认的加载方式,延迟加载机制是为了避免一些无谓的性能开销而提出来的,所谓延迟加载就是当在真正需要数据的时候,才真正执行数据加载操作

  • C#中的索引器的简单理解和用法

    C#中的类成员可以是任意类型,包括数组和集合。当一个类包含了数组和集合成员时,索引器将大大简化对数组或集合成员的存取操作

  • 深入C# 序列化(Serialize)、反序列化(Deserialize)

    C#中的序列化和反序列化,序列化是.NET运行时环境用来支持用户定义类型的流化的机制