去除重复数

   这是一道外企算法的面试题，前提是不允许使用util包之外的类，即任何集合类都不允许使用。 写出的算法效率越高，此题得分越高，大家可以试一下。题目是输入一串已经排序好的数组，输出消除重复数之后的数组。如：
输入{ 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5 };输出{ 1, 2, 3, 4, 5 };

/**
 * 消除重复数(已经排序好的数组)
 * 
 * @author fangtengfei
 * @date   2010-5-16
 */
public class Distinct {

	public static void main(String[] args) {
		int[] oNums = { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5 };
		int[] newNums = new int[oNums.length] ;
		int count = 0,index=-1;
		for (int i = 0; i  count) {
		  newNums[++index]=oNums[i];
		  count = oNums[i];
		}
		
	}
}

评论

11 楼 adherence 2010-09-13  

我想问一下，如果数组是这样的呢：

int[] oNums = { 1, 2, 4, 4, 3, 3,5, 2, 4, 4, 5, 2, 3, 5, 5 };

也就是说不规律的应该怎么解决？

10 楼 rink1969 2010-09-03  

既然是排序的，应该是二分查找比较快吧
简单的写了一个，边界条件什么的也没仔细考虑
递归调用不知道对性能影响大不大？

#include <stdio.h>

int data[]={1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5};

int bin_comp(int * pdata,int len)
{
	int mid,midindex;

	midindex = len/2;
    mid = pdata[midindex];

    if(pdata[0] == pdata[len])
	{
		return 0;
	}

	if (mid == pdata[len])
	{
        bin_comp(pdata,midindex);
		return 0;
	}

	if (mid == pdata[0])
	{        
        bin_comp(pdata+midindex,midindex);
		return 0;
	}
	
    //if ((mid != pdata[0]) && (mid != pdata[len]))
	{
		bin_comp(pdata,midindex);
		printf("%d    ",mid);
        bin_comp(pdata+midindex,midindex);
	}

	return 0;    
}

main()
{
	int count = sizeof(data)/sizeof(data[0]);

	printf("%d    ",data[0]);
	bin_comp(data,count-1);
	printf("%d    ",data[count-1]);
}

9 楼 fantasy 2010-09-01  

BestUpon 写道

java的set早就做好了！不用那么麻烦！

这是一道外企算法的面试题，前提是不允许使用util包之外的类，即任何集合类都不允许使用。
写出的算法效率越高，此题得分越高，大家可以试一下。

8 楼 BestUpon 2010-09-01  

ps：代码质量：
1，泛型
2，对象for
3，…

7 楼 BestUpon 2010-09-01  

java的set早就做好了！不用那么麻烦！

6 楼 fantasy 2010-07-02  

yutian2211 写道

如果是无序的数组，如何做效率高一点呢？

通过hashtable算法。

5 楼 yutian2211 2010-07-01  

如果是无序的数组，如何做效率高一点呢？

4 楼 fantasy 2010-05-23  

用SET就不是在写一个算法了，而是在用别人的算法。

3 楼 harry2007 2010-05-22  

直接用SET不就可以了？

2 楼 fantasy 2010-05-21  

sorry!我没写清楚，是已经排序好的数组。

1 楼 java_lin 2010-05-21  

public class Distinct {  
 
    public static void main(String[] args) {  
        int[] oNums = { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5 };  
        List newNums = new ArrayList();  
        int count = 0;  
        for (int i = 0; i < oNums.length; i++) {  
            if (oNums[i] > count) {  
                newNums.add(oNums[i]);  
                count = oNums[i];  
            }  
        }  
    }  
} 



不知道LZ想做个什么,你试想
int[] oNums = { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5 };  

如果oNums 数组第一个数大于后面的数.会出什么结果吗???