1
每日一
1.已知线性表(a1 a2 a3 …an)按顺序存于内存,每个元素都是整数,试设计用最少时间把所有值为负
数的元素移到全部正数值元素前边的算法:例:(x,-x,-x,x,x,-x …x)变为(-x,-x,-x…x,x,x)。
类似本题的另外叙述有:
(1)设有一元素为整数的线性表 L=(a 1 ,a 2 ,a3,…,a n ),存放在一维数组 A[N]中,设计一个算法,以表中 a n 作为参考元素,将该表分为左、右两部分,其中左半部分每个元素小于等于 a n ,右半部分每个元素都大于 a n , a n位于分界位置上(要求结果仍存放在 A[N]中)。
(2)顺序存储的线性表 A,其数据元素为整型,试编写一算法,将 A 拆成 B 和 C 两个表,使 A 中元素值大于等于 0 的元素放入 B,小于 0 的放入 C 中.. 要求:
1)表 B 和 C 另外设置存储空间;
2)表 B 和 C 不另外设置,而利用 A 的空间.
(3)知线性表(a1, a2,a3,…,an)按顺序存储,且每个元素都是整数均不相同,设计把所有奇数移到所有偶数前边的算法。(要求时间最少,辅助空间最少)
(4) 编写函数将一整数序列中所有负数移到所有正数之前,要求时间复杂度为 O(n)
(5) 已知一个由 n ( 设 n=1000)个整数组成的线性表,试设计该线性表的一种存储结构,并用标准 pascal语言描述算法,实现将 n 个元素中所有大于等于 19 的整数放在所有小于 19 的整数之后。要求算法的时间复杂度为 O(n),空间复杂度 O(1)。
正确答案
ps:||代表注释
1.[题目分析]题目要求重排n个元素且以顺序存储结构存储的线性表,使得所有值为负数的元素移到正数元素的前面。这可采用快速排序的思想来实现,只是提出暂存的第一个元素(枢轴)并不作为以后的比较标准,比较的标准是元素是否为负数。
int Rearrange(SeqList a; int n)∥a是具有n个元素的线性表,以顺序存储结构存储,线性表的元素是整数。本算法重排线性表a,
∥使所有值为负数的元素移到所有值为正数的数的前面。
{i=0; j=n-1; ∥ i,j为工作指针(下标),初始指向线性表a的第1个和第n个元素。
t=a[0]; ∥暂存枢轴元素。
while(i<j)
{ while(i<j && a[j]>=0) j--; ∥ 若当前元素为大于等于零,则指针前移。
if(i<j){a[i]=a[j];i++;} ∥ 将负数前移。
while(i<j &&a[i]<0)i++; ∥ 当前元素为负数时指针后移。
if(i<j) a[j--]=a[i]; ∥ 正数后移。
}
a[i]=t; ∥将原第一元素放到最终位置。
}
[算法讨论] 本算法时间复杂度为O(n)。算法只是按题目要求把正负数分开,如要求统计负数和大于等于零的个数,则最后以t来定。如t为负数,则0至i共i+1个负数,n-1-i个正数(包括零)。另外,题目并未提及零的问题,笔者将零放到正数一边。对此问题的扩充是若元素包含正数、负数和零,并要求按负数、零、正数的顺序重排线性表,统计负数、零、正数的个数。请读者利用上面解题思想自行解答。
类似本题的选了5 个题,其解答如下:
(1)与上面第8题不同的是,这里要求以a n 为参考元素,将线性表分成左右两部分。左半部分的元素都小于等于a n ,右半部分的元素都大于a n ,a n 位于分界位置上。其算法主要片段语句如下:
i=1;j=n;
t=a[n]; ∥暂存参考元素。
while(i<j)
{ while(i<j && a[i]<=t) i++; ∥当前元素不大于参考元素时,指针i后移。
if(i<j) a[j--]=a[i]; ∥将大于参考元素的元素后移。
while(i<j && a[j]>t) j--; ∥当前元素大于参考元素时指针前移。
if(i<j) a[i++]=a[j]; ∥将小于参考元素的当前元素前移。
}
a[i]=t; ∥参考元素置于分界位置。
(2) [题目分析]本题要求将线性表A分成B和C两个表,表B和表C不另占空间,而是利用表A的空间,其算法与第8题相同。这里仅把表B和表C另设空间的算法解答如下:
void Rearrange2( int A[],B[],C[])∥线性表A有n个整型元素,顺序存储。本算法将A拆成B和C 两个表,B中存放大于
∥等于零的元素,C中存放小于零的元素。
{i=0; ∥i,j,k是工作指针,分别指向A、B和C表的当前元素。
j=k=-1; ∥j,k初始化为-1。
while(i<n)
{ if(A[i]<0) C[++k]=A[i++]; ∥将小于零的元素放入C表。
else B[++j]=A[i++]; ∥将大于零的元素放入B表。
[算法讨论]本题用一维数组存储线性表,结果线性表B和C中分别有j+1和k+1个元素。若采用教材中的线性表,则元素的表示作相应改变,例如A.elem[i],而最后B和C表应置上表的长度,如B.length=j和C.length=k。
(3) 本题与第8题本质上相同,第8题要求分开正数和负数,这里要求分开奇数和偶数,判别方式是
a[i]%2==0,满足时为偶数,反之为奇数。
(4) 本题与第8题相同,只是叙述不同。
(5) 本题与第8题基本相同,不同之处在于这里的分界元素是整数19(链表中并不要求一定有19)。本题要求用标准pascal描述算法,如下所示。
TYPE arr= ARRAY[1..1000] OF integer;
VAR a:arr;
PROCEDURE Rearrange5(VAR a:arr);
∥a是n(设n=1000)个整数组成的线性表,用一维数组存储。本算法将n个元素中所有大于等于19的整数放在所有小于19的整数之后。
VAR i,j,t:integer;
BEGIN
i:=1;j:=n;t:=a[1] ;∥i,j指示顺序表的首尾元素的下标,t暂存分界元素
WHILE(i<j) DO
BEGIN
WHILE (i<j) AND(a[j]>=19) DO j:=j-1;
IF(i<j) THEN BEGIN A[i]:=A[j];i:=i+1 END;
WHILE (i<j) AND(a[i] <19) DO i:=i+1;
IF(i<j) THEN BEGIN A[j]:=A[i];j:=j-1 END;
END;
a[i]:=t;
END;
[算法讨论] 分界元素t放入a[i],而不论它的值如何。算法中只用了一个t中间变量,符合空间复杂度O(1)的要求。算法也满足时间复杂度O(n)的要求。
如果您觉得本篇文章对您有作用,请转发给更多的人,点一下好看就是对小编的最大支持!
-end-