去除重复数

fantasy

浏览: 513721 次
性别:
来自: 杭州

最近访客更多访客>>

happy_wally

dy.f

韩美艳

sin_yaksa

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

算法

算法面试

这是一道外企算法的面试题，前提是不允许使用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];
		}
		
	}
}

分享到：

有序数组中绝对值不同的数的个数 | 括号匹配

2010-05-20 18:00
浏览 2144
评论(31)
论坛回复 / 浏览 (30 / 11112)
分类:编程语言
查看更多

31 楼 houyu533 2012-11-16

跳跃表吧！

30 楼 codeincoffee 2011-05-02

fivestarwy 写道

排序好的，最快应该是二分吧

二分相对于遍历来说，是需要空间来换时间的。二分需要建立一个O(N)的数组。而遍历可以不需要。

这是二分的代码：

public static void removeDuplicationByBinary(int[] src, int start, int end, int[] array) {
		if (start >= end) return;
		int middle = (end - start)/2;
		if (src[middle] != src[src[0]]) {
			src[src[0]++] = src[middle];
			return;
		}
		removeDuplicationByBinary(src, middle, end, array);
		removeDuplicationByBinary(src, start, middle, array);
	}
	
	public static int[] removeDuplicationByBinary(int[] src) {
		if (src == null || src.length < 2) return src;
		int[] array = new int[src.length+1];
		removeDuplicationByBinary(src, 0, src.length-1, array);
		int[] result = new int[array[0]];
		System.arraycopy(array, 1, result, 0, array[0]+1);
		return result;
	}

29 楼 fivestarwy 2011-05-01

排序好的，最快应该是二分吧

28 楼 codeincoffee 2011-05-01

sunney2012 写道

int[] a = { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5 };
int[] bucket = new int[a.length];
for (int i = 0; i < a.length; i++) {
bucket[a[i]] = a[i];
}

如果a[i]是负数，会出错的，同学。

我能给出的最好答案只有这样了：

public static int[] removeDuplication(int[] src) {
		if (src == null || src.length < 2) return src;
		int index = 0;
		for (int i = 1; i < src.length; i++) 
			if (src[i] != src[index]) //这里(src[i]^src[index])!=0会不会更快？
				src[++index] = src[i];
		int[] result = new int[index+1];
		System.arraycopy(src, 0, result, 0, index+1);
		return result;
}

27 楼 jinceon 2011-05-01

buptwhisper 写道

遍历一次,n难道比nlg(n) 慢？在n的规模在数十或者更大时，不是n要比nlg(n)小么。。

我也觉得，有时候，一听到算法，效率什么的，就去想啊想，却偏偏不去考虑最普通的方法。有点为了算法而算法的感觉

26 楼 ggzwtj 2011-03-18

这个也叫算法。。。

25 楼 buptwhisper 2011-03-18

遍历一次,n难道比nlg(n) 慢？在n的规模在数十或者更大时，不是n要比nlg(n)小么。。

24 楼 sunney2012 2011-03-12

int[] a = { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5 };
int[] bucket = new int[a.length];
for (int i = 0; i < a.length; i++) {
bucket[a[i]] = a[i];
}

23 楼 wkshippou 2011-03-07

先分组，再将分组中list.size大于1的从最后一个删除到第一个,只保留第一个，这样就没有重复的了。
QQ：784222511

22 楼宋建勇 2011-02-25

package test;

public class Distinct {

    public static void main(String[] args) {
        int[] oNums = {-3,-3,-3,-2,-1,0,0,0,0,0, 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5,7,8,8,8,8,9 };
        String a=String.valueOf(oNums[0])+",";
        for(int i=1;i<oNums.length;i++){
        String b[] = a.split(",");
        if(oNums[i]!=Integer.parseInt(b[b.length-1]))
        a=a+oNums[i]+",";
        }
        System.out.println(a.replace(',', ' '));
    }
}

21 楼宋建勇 2011-02-25

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];
            }
        }
    }
}

以上中如果将
int[] oNums = { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5 };
改为
int[] oNums = {0, 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5 };
将会丢失第一个数字（0）

20 楼 sadawn 2011-02-25

排序好的数组，只需要遍历一次就可以了，拿当前的值与上一个值比较，就可以去除重复的数字，比较常规的做法

arr = [1,1,1,2,2,6,6,6,34,88,88,99,101]
newArr =[]
newArr.append(arr[0])

for i in arr[1:]:
    if i != newArr[len(newArr)-1]:
        newArr.append(i)

print newArr

19 楼 ray_linn 2011-02-24

求模呗....hash算法

18 楼 jiminsc 2011-02-24

有一个取巧的方法，楼主参考下

	public static void main(String[] args) {
		//质数数组
		int[] prime = new int[] { 2, 3, 5, 7, 11, 13, 17 };
		//目标数据
		int[] data = { 6, 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5 };
		long tmp = 1;
		for (int i = 0; i < data.length; i++) {
			if (tmp % prime[data[i]] != 0) {
				System.out.println(data[i]);
				tmp *= prime[data[i]];
			}
		}
	}

17 楼 luobin23628 2010-12-08

我的做法，参考合并排序递归把数组分成两半，然后再合并数组，效率nlgn。
合并数组的规则
1. 找出前一个数组中最后一个不为-1的数(这里用-1标志重复位)
2. 如果找不到，则直接合并
3. 如果找到这个数，则从下一个数组的开始位置开始，找出重复的数,置为-1。

	public static void main(String[] args) {
		int[]x = new int[]{1,1,2,3,3,3,4,4,4,4,4,5,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6,6};
		distinct(x, 0, x.length);
		System.out.println(Arrays.toString(x));
	}
	
	public static void distinct(int[] x,int p,int q){
		if(p==q-1){
			return;
		}
		int r = (p+q)>>>1;
		distinct(x, p, r);
		distinct(x, r, q);
		merge(x, p, r, q);
	}
	
	private static void merge(int[] x,int p,int r,int q){
		int key = -1;
		int k = r-1;
		while(k>=p){
			if(x[k]!=-1){
				key = x[k];
				break;
			}
			k--;
		}
		if(key!=-1){
			while(r<q&&(x[r]==key||x[r]==-1)){
				x[r] = -1;
				r++;
			}
		}
	}
         没有直接遍历快。。不过也是一个思路

16 楼 cozilla 2010-12-06

<p>
</p>
<pre name="code" class="java"> private static int[] num = { 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 4, 4, 4, 5,
6, 7, 7, 7 };

public static void main(String args[]) {
bSearch(0, num.length - 1);
}

public static void bSearch(int left, int right) {
if (left > right)
return;
if (num[left] == num[right]) {
System.out.print(num[right]);
return;
}
int mid = (left + right) / 2;
if (num[left] == num[mid]) {
bSearch(mid, right);
} else if (num[mid] == num[right]) {
bSearch(left,mid);
} else {
int lower = lowerBound(left,mid);
int upper = upperBound(mid,right);
bSearch(left, lower-1);
System.out.print(num[mid]);
bSearch(upper+1, right);
}

}

private static int upperBound(int left, int right) {
if(num[left]== num[right])return right;
int mid = (left + right) / 2;
if(left == mid){ //即right= left+1
return left;
}
if(num[left]==num[mid])
return upperBound(mid,right);
else
return upperBound(left,mid);
}

private static int lowerBound(int left, int right) {
if(num[left]== num[right])return left;
int mid = (left + right) / 2;
if(left == mid){ //即right= left+1
return right;
}
if(num[mid]==num[right])
return lowerBound(left,mid);
else
return lowerBound(mid,right);
}</pre>

15 楼 cozilla 2010-12-06

我觉得这道题目O（n）肯定不是最好的算法。
用二分搜索来者可以效率更高

14 楼 yiyidog125 2010-10-20

这题和binary search有什么关系呢
这个数组是排好序的　直接相邻位比较就好了

   int[] removeDuplicates(int[] values)
   {
int current = 0;
int prev = current-1;
int count = 0;
int[] temp = new int[values.length];
for (int i = 0; i < values.length; i++) {
prev = current;
current = values[i];
if (current != prev) {
temp[count++] = current;
}
}
int[] result = new int[count];
System.arraycopy(temp, 0, result, 0, count);
temp = null;
return result;
   }

13 楼 terry12903 2010-10-14

 def sort(list):
    sortList=[]
    for i in list:
        if sortList.count(i)==0:
            sortList.append(i)

    print(sortList)

12 楼 gteam.yu 2010-09-16

10楼的朋友的忽略了1,1,1的情况吧，用递归是没有错了，我自己写了一个java版本的，贴上（注释没有写，抱歉了）
public static void main(String[] args) {
int[] ints = { 1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 4, 4, 4, 5, 6, 7, 7, 7 };
distinct(ints, 0, ints.length - 1);
}
//递归、折半查找排除
public static void distinct(int[] ints, int sIndex, int eIndex) {
int midIndex = (eIndex + sIndex) / 2;
if (ints[sIndex] == ints[eIndex]) {
    System.out.println(ints[sIndex]);
} else if (ints[midIndex] == ints[sIndex] && ints[midIndex] != ints[midIndex + 1]) {
    System.out.println(ints[midIndex]);
    distinct(ints, midIndex + 1, eIndex);
//不断的向右缩减成员，把2,2,2,2,3变成2,3
} else if (ints[sIndex] == ints[sIndex + 1]) {
    distinct(ints, sIndex + 1, eIndex);
} else {
    System.out.println(ints[sIndex]);
distinct(ints, sIndex + 1, eIndex);
    }
}

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论