1-1000中放在含有1001个元素的数组中,只有唯一的一个元素重复,其他均只出现一次. 设计一个算法,将它找出来
四种方法来求解该题
数组排序法
先将数组排序,当相邻两个值相等时,则将该值输出变为所求值
异或法
涉及到算法(相同的值异或为0;0与任意值异或后值不变)
* 1-1000的值与1-1001的值异或,
* 这些数包含999对相同的数与一个包含了3个数
* 相同的数异或为0,所以999对数异或完为0,三个数其中两个数异或也为0,0与要求的数异或即可得出所求的值
标记法
通过标记来标记数组中哪个值出现了两次,之后再将标记两次的角标输出即为重复的值
求和法
参考:求连续数组中唯一重复的元素
只谈思路,程序未实现.
思路:通过将1-1001个元素相加,之后再减去1-1000的连续元素,求得的值即为所要求得重复值
import java.util.Arrays;
import java.util.Random;
/**
* 1-1000中放在含有1001个元素的数组中,只有唯一的一个元素重复,其他均只出现一次. 设计一个算法,将它找出来
*
* @author Clearlight
*
*/
public class UniqueNum {
public static void main(String[] args) {
int[] arr = specArr(1001);
SortMethod(arr);
exclusiveOrMethod(arr, arr.length);
signMethod(arr, arr.length);
}
/**
* 产生一个指定大小的数组,并且其中只包含一个重复的值
*
* @param size 数组的大小
* @return 返回一个含有重复值的随机数组
*/
public static int[] specArr(int size) {
int[] arr = new int[size];
for (int i = 0; i < arr.length; i++) {
arr[i] = i + 1;
}
// 最后一个数,是随机数
arr[arr.length - 1] = new Random().nextInt(size - 1) + 1;// (N-1)随机产生0-999之间的值,+1后为1-1000的值
// 随机下标
int index = new Random().nextInt(size);// 随机产生0-1000之间的值
System.out.println("重复的值:" + arr[arr.length - 1]);
// 将随机产生的下标的值与arr.length-1的值相交换,形成一个随机产生的特定重复的数组
int i = 0;
i = arr[index];
arr[index] = arr[arr.length - 1];
arr[arr.length - 1] = i;
return arr;
}
/**
* 第一种方法思路: 通过排序,当相邻两个值相等时,则将该值输出变为所求值
*
* @param arr 该数组中含有特定重复的一个值
*/
public static void SortMethod(int[] arr) {
Arrays.sort(arr);
for (int j = 0; j < arr.length; j++) {
if (arr[j] == arr[j + 1]) {
System.out.println(arr[j]);
break;
}
}
}
/**
* 第二种方法思路: 涉及到算法(相同的值异或为0;0与任意值异或后值不变)
* 1-1000的值与1-1001的值异或,
* 这些数包含999对相同的数与一个包含了3个数
* 相同的数异或为0,所以999对数异或完为0,三个数其中两个数异或也为0,0与要求的数异或即可得出所求的值
*
*
* @param arr 该数组中含有特定重复的一个值
* @param size 数组的大小
*/
public static void exclusiveOrMethod(int[] arr, int size) {
int x = 0;
for (int i = 1; i <= size - 1; i++) {
x = (x ^ i);
}
for (int i = 0; i < size; i++) {
x = x ^ arr[i];
}
System.out.println(x);
}
/**
* 第三个方法思路:通过标记来找出重复出现的值
*
* @param arr 该数组中含有特定重复的一个值
* @param size 数组大小
*/
public static void signMethod(int[] arr, int size) {
int[] helper = new int[size];
for (int i = 0; i < size; i++) {
helper[arr[i]]++;// 将1-1000所处出现的值所一个计数
}
for (int i = 0; i < size; i++) {
if (helper[i] == 2) {// 当其中有值出现两次即数组大小为2,输出角标即可
System.out.println(i);
break;
}
}
}
}
输出结果:
Note:由于重复的值为随机产生,故每次输出都不同