在其它数都出现k次的数组中找到只出现一次的数题目：思路：代码：

66 阅读 0 评论 44 点赞

我是靠谱客的博主醉熏花瓣，最近开发中收集的这篇文章主要介绍在其它数都出现k次的数组中找到只出现一次的数题目：思路：代码：，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目：

给定一个整形数组arr和一个大于1的整数k。已知arr中只有1个数出现了1次，其他的数都出现了k次，请返回只出现1次的数。

思路：

根据该题的数组中很多数出现了k次只有一个数出现了1次。可以采用如下的步骤解决此题。

将数组中所有的数都转换为k进制的形式。
所有的数依次相加取余。
最终的结果为只出现一次的数。

为何将所有的数相加并取余后得到的结果就是只出现1次的书。设x为出现了k次的k进制数。k个取余的x相加即k*(x%k)。其结果必然为0.也就是但凡在数组中出现了k次的数再数组中所有的数进行取余相加操作后都会消失，剩下的自然就是只出现1次的数。

代码：

/**
     * 在其它数都出现k次的数组中找到只出现一次的数
     */
	public int getOneFromN(int [] arr,int k){
		if(arr == null || k <= 1)
			return 0;
		
		int [] cur = new int [32];
		for(int i=0;i<arr.length;i++){
			addAnddivide(cur, arr[i], k);
		}
		int num = transferIntoInteger(cur);
		return num;
	}
	
	/**
	 * k进制数相加取余
	 */
	public void addAnddivide(int [] cur,int value,int k){
		int [] res = transferintoK(value, k);
		for(int i = 0;i<res.length;i++){
			cur[i] = (cur[i] + res[i]) % k;
		}
	}
	
	/**
	 * 转换为k进制的数
	 */
	public int [] transferintoK(int n,int k){
		int [] res = new int [32];
		int index = 0;
		while(n != 0){
			res[index++] = n%k;
			n /= k;
		}
		return res;
	}
	
	/**
	 * 数组转换为整数
	 */
	public int transferIntoInteger(int [] nums){
		int num = 0;
		for(int i = nums.length - 1;i>=0;i--){
			num = num * 10 + nums[i];
		}
		return num;
	}