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;
}
}
}
} 輸出結果:
