博客

首先给出暴力方法，平方性能

	public static int count(Comparable[] a) {
		
		//统计重复元素数，如果元素后面没有和它一样的那么它就是不重复元素，否则不是
		int count = 0;
		for(int i = 0;i<a.length;i++) {//判断0到N-1这些元素是不是重复的
			for(int j = i+1;j<a.length;j++) {
				if(a[j]==a[i]) {
					count++;//a[i]是重复元素
					break;
				}
			}
		}
		return count;
	}

对于这个问题，还有一种线性对数性能的解决办法，即先排序，再统计，代码如下

	public static int count(Comparable[] a) {
		Quick.sort(a);//快速排序
		
		//统计不重复元素数
		int count = 1;
		for(int i = 1;i<a.length;i++) {//第一个元素必然要计数
			if(a[i].compareTo(a[i-1]) != 0) {//和前一个元素重复则不计数
				count++;
			}
		}
		
		return a.length-count;
	}