今日面试题:又见排序

给定大小为n的数组A,A中的元素有正有负。请给出方法,对其排序,保证:

1. 负数在前面,正数在后面

2. 正数之间相对位置不变

3. 负数之间相对位置不变

能够做到时间复杂度为O(n),空间复杂度为O(1)么?

=======================================================

数组和分析

原题

有数组A={5,3,8,9,16},第一次遍历有:A = {3-5,8-3,9-8,16-9}={-2,5,1,7},数组中元素和为-2+5+1+7=11;第二次遍历有:A = {5-(-2),1-5,7-1}={7,-4,6},元素和为9. 给定数组A,求第n次遍历之后,数组中元素的和。

分析

处理这样的题目,如果没有直接知道相关的原理,可以自己走一下一些具体的例子,这样就可以发现一些规律,根据这些规律,再去联想解决的完整方法。

经过观察,我们可以发现:

  • 对于第k次遍历而言,x_k_1、x_k_2、...、x_k_m,sum = x_k_m - x_k_1

也就是说,第k次遍历结果的和,只与第一个和最后一个元素先关。下面,就来讨论,如何求得第一个和最后一个元素。 我们看题目中的例子,先考虑第一个元素的变化

  • 第一次遍历 k = 1时:-2=3-5

  • 第二次遍历 k = 2时:7=5-(-2)=(8-3)-(3-5)=8-2*3+5

  • 第三次遍历 k = 3时:-11=-4-7=(1-5)-(5-(-2)) = ((9-8)-(8-3)) - ((8-3)-(3-5))=9-3*8+3*3-5

分析到此,想必大家已经能够明白这其中的规律,其实就是杨辉三角,老外叫帕斯卡三角。最后一个节点是类似的。而且,真个方法的时间复杂度与遍历的次数n有关,与数组的大小无关。

【注】杨辉三角,在杨辉的《九章算术》中有记载,那时还叫贾宪三角,只不过后来杨辉的名字非常大,渐渐叫杨辉三角的越来越多。

【分析完毕】

本文来自微信:待字闺中,2013-09-02发布,原创@陈利人 ,欢迎大家继续关注微信公众账号“待字闺中”。