给定数组A，大小为n，数组元素为1到n的数字，统计哪些数字没有出现，哪些数字出现了多少次

1. 给定数组A，大小为n，数组元素为1到n的数字，不过有的数字出现了多次，有的数字没有出现。请给出算法和程序，统计哪些数字没有出现，哪些数字出现了多少次。能够在O(n)的时间复杂度，O(1)的空间复杂度要求下完成么？

分析：如果对时间复杂度没有要求，那么先排序再统计就ok，时间O(n*lgn)，空间O(1)。如果对空间没有要求，那么使用位图或者哈希表，时间O(1)，空间O(n)。但是题目对两个都有要求，那么只能是在原数组进行统计才能满足O(1)的空间复杂度。

            首先想到的是类似计数排序的方法，问题的关键在于区分计数值和原来的值。比如，A[0]=5，那么A[4]存储5的计数应该加1，但是A[4]此时还存储有其它值，该怎么办？

            有两种方法，第一种非常巧妙，实在是叹为观止！第二种使用另一种方法区分计数和原值。思路都是一样的。

public class StatisArray {
	//给定数组A，大小为n，数组元素为1到n的数字，统计哪些数字没有出现，哪些数字出现了多少次
	public static void statis1(int[] A){
		if(A==null || A.length==0) return;
		int n = A.length;
		for(int i=0; i<n; i++)	//使每个元素对n求余得到其位置，同时避免A[0]==n造成的错误
			A[i]--;
		for(int i=0; i<n; i++){	//使用+n来计数，对n求余得到原值，除以n得到计数
			A[A[i]%n] += n;
		}
		for(int i=0; i<n; i++){
			System.out.println((i+1)+" occurs "+(A[i]/n)+" times.");
		}
		/*for(int i=0; i<n; i++){	//使用+2n来计数，对n求余得到原值，除以2n得到计数，避免A[0]==n造成的错误
			A[A[i]%n] += n<<1;
		}
		for(int i=1; i<n; i++){
			System.out.println(i+" occurs "+(A[i]/(n<<1))+" times.");
		}
		System.out.println(n+" occurs "+(A[0]/(n<<1))+" times.");*/
	}
	
	public static void statis2(int[] A){
		if(A==null || A.length==0) return;
		
		int n = A.length;	
		for(int i=0; i<n; i++){
			if(A[i]>n) continue;
			if(A[i] == i+1)	{A[i] = n+1; continue;}
			
			int t = A[i], j = t-1; //t要放到对应位置的值，j要放的位置
			while(true){
				if(j<=i) {if(A[j]>n) A[j]++; else A[j]=n+1; break;}//转了一圈回到当前或之前的位置，break掉，防止错误累加
				if(A[j]==t) A[j]=n+1; //对应位置原本就是自己，则计数
				if(A[j]>n) {A[j]++; break;}  //对应位置已经是计数，则自增并break
				int tmp = A[j];
				A[j] = n+1;
				t = tmp;
				j = t-1;
			}
		}
		for(int i=0; i<n; i++)
			System.out.println((i+1)+" occurs "+(A[i]>n ? A[i]-n : 0)+" times.");
	}
	public static void main(String[] args){
		int A[] = {5,1,1,2,4};
		//statis1(A);
		statis2(A);
	}
}

最后

以上就是贤惠云朵为你收集整理的给定数组A，大小为n，数组元素为1到n的数字，统计哪些数字没有出现，哪些数字出现了多少次的全部内容，希望文章能够帮你解决给定数组A，大小为n，数组元素为1到n的数字，统计哪些数字没有出现，哪些数字出现了多少次所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。