庄周梦蝶

生活、程序、未来
   :: 首页 ::  ::  :: 聚合  :: 管理

一道面试题注记

Posted on 2010-10-28 10:53 dennis 阅读(2993) 评论(8)  编辑  收藏 所属分类: 数据结构与算法计算机科学与基础
   
    javaeye的一个帖子介绍一道面试题,取数组的最大元素和前n个大元素,取最大元素很简单,遍历即可。取前N大元素,可以利用排序,最简单的实现:

    public static int[] findTopNValues(int[] anyOldOrderValues, int n) {
        Arrays.sort(anyOldOrderValues);
        
int[] result = new int[n];
        System.arraycopy(anyOldOrderValues, anyOldOrderValues.length 
- n,
                result, 
0, n);
        
return result;
    }
   
     Arrays.sort(int[])使用的是快排,平均的时间复杂度是O( n lg(n)),在一般情况下已经足够好。那么有没有平均情况下O(n)复杂度的算法?这个还是有的,这道题目其实是选择算法的变形,选择一个数组中的第n大元素,可以采用类似快排的方式划分数组,然后只要在一个子段做递归查找就可以,平均状况下可以做到O(n)的时间复杂度,对于这道题来说稍微变形下算法即可解决:

    /**
     * 求数组的前n个元素
     * 
     * 
@param anyOldOrderValues
     * 
@param n
     * 
@return
     
*/
    
public static int[] findTopNValues(int[] anyOldOrderValues, int n) {
        
int[] result = new int[n];
        findTopNValues(anyOldOrderValues, 
0, anyOldOrderValues.length - 1, n,
                n, result);
        
return result;
    }

    
public static final void findTopNValues(int[] a, int p, int r, int i,
            
int n, int[] result) {
        
// 全部取到,直接返回
        if (i == 0)
            
return;
        
// 只剩一个元素,拷贝到目标数组
        if (p == r) {
            System.arraycopy(a, p, result, n 
- i, i);
            
return;
        }
        
int len = r - p + 1;
        
if (i > len || i < 0)
            
throw new IllegalArgumentException();
        
// if (len < 7) {
        
// Arrays.sort(a, p, r+1);
        
// System.arraycopy(a, r - i+1 , result, n - i, i);
        
// return;
        
// }

        
// 划分
        int q = medPartition(a, p, r);
        
// 计算右子段长度
        int k = r - q + 1;
        
// 右子段长度恰好等于i
        if (i == k) {
            
// 拷贝右子段到结果数组,返回
            System.arraycopy(a, q, result, n - i, i);
            
return;
        } 
else if (k > i) {
            
// 右子段比i长,递归到右子段求前i个元素
            findTopNValues(a, q + 1, r, i, n, result);
        } 
else {
            
// 右子段比i短,拷贝右子段到结果数组,递归左子段求前i-k个元素
            System.arraycopy(a, q, result, n - i, k);
            findTopNValues(a, p, q 
- 1, i - k, n, result);
        }
    }

    
public static int medPartition(int x[], int p, int r) {
        
int len = r - p + 1;
        
int m = p + (len >> 1);
        
if (len > 7) {
            
int l = p;
            
int n = r;
            
if (len > 40) { // Big arrays, pseudomedian of 9
                int s = len / 8;
                l 
= med3(x, l, l + s, l + 2 * s);
                m 
= med3(x, m - s, m, m + s);
                n 
= med3(x, n - 2 * s, n - s, n);
            }
            m 
= med3(x, l, m, n); // Mid-size, med of 3
        }
        
if (m != r) {
            
int temp = x[m];
            x[m] 
= x[r];
            x[r] 
= temp;
        }
        
return partition(x, p, r);
    }

    
private static int med3(int x[], int a, int b, int c) {
        
return x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a)
                : x[b] 
> x[c] ? b : x[a] > x[c] ? c : a;
    }

    
public static void swap(int[] a, int i, int j) {
        
int temp = a[i];
        a[i] 
= a[j];
        a[j] 
= temp;
    }

    
public static int partition(int a[], int p, int r) {
        
int x = a[r];
        
int m = p - 1;
        
int j = r;
        
while (true) {
            
do {
                j
--;
            } 
while (j>=p&&a[j] > x);
            
do {
                m
++;
            } 
while (a[m] < x);
            
            
if (j < m)
                
break;
            swap(a, m, j);
        }
        swap(a, r, j 
+ 1);
        
return j + 1;
    }
 选择算法还有最坏情况下O(n)复杂度的实现,有兴趣可以读算法导论和维基百科。题外,我测试了下这两个实现,在我的机器上大概有2倍多的差距,还是很明显。


评论

# re: 一道面试题注记  回复  更多评论   

2010-11-01 00:26 by yangwm
你给出的算法, 源码不全, 理解不了。

我也写了一个,可以看我的博客《最大N算法(前一版本的改进)》:
MaxNAlgorithm比最简单的排序后取最大的n位, 效率高十陪以上(当然需排序结果也要有足够大才行; 测试结果只是个比较而已,因为vm没有先预热以及相应参数配置)。

# re: 一道面试题注记  回复  更多评论   

2010-11-01 09:28 by denniis
@yangwm
这源码很全了吧……

# re: 一道面试题注记  回复  更多评论   

2010-11-01 09:35 by dennis
@yangwm
不好意思,是遗漏来med3这个方法,补上。这个算法跟快排的分治算法是一样的,快排可以用的那些优化手段也可以在这里用上。

# re: 一道面试题注记  回复  更多评论   

2010-11-01 09:41 by dennis
@yangwm
我测试下我的实现,大概比你的那个实现还快上4-5倍,不过你的实现多了一个box/unbox的开销,本身就不公平。当然,我上面提到来,我的这个实现还有改进的空间:改进划分算法,当子段小的时候不做递归而做排序等等。

另外就是我的结果集合是没有排序的,你的测试程序只输出前10个,因此看起来结果不同,将结果全部排序并输出即可验证我的程序也是正确的。

# re: 一道面试题注记  回复  更多评论   

2010-11-01 22:13 by yangwm
我的那个算法改为基本类型版的吧。
同时与你的你的算法做了一下对比测试。
实现比你的还快一些。

# re: 一道面试题注记  回复  更多评论   

2010-11-01 22:15 by yangwm
http://blog.csdn.net/yang_net/archive/2010/11/01/5978488.aspx

# re: 一道面试题注记[未登录]  回复  更多评论   

2010-11-01 23:24 by dennis
@yangwm

说快或者说慢,总有个前提,以你的代码为例,取前10个,是你的会快一些,而取前10000个,却是我的快很多。此外,优秀的算法还需要考虑其他情况,比如数组的重复元素比较多,比如数组已经排序等等。我改进了一下划分算法,有兴趣可以再测试看看。

# re: 一道面试题注记  回复  更多评论   

2010-11-01 23:42 by dennis
@yangwm
1000万取前10万个,你的实现性能下降很惊人,比较奇怪。而我的这个实现可以在任意维度下维持一个优秀的性能,包括各种特殊情况:数组已经排序、数组重复元素非常多等。

只有注册用户登录后才能发表评论。


网站导航: