剣指offer面接問題3-配列で繰り返される数字java
タイトルの説明
長さnの配列のすべての数字は0からn-1の範囲内にある.配列のいくつかの数字は重複していますが、いくつかの数字が重複していることは分かりません.数字ごとに何回繰り返されるか分からない.配列のいずれかの重複する数字を見つけてください.例えば、長さ7の配列{2,3,1,0,2,5,3}を入力すると、対応する出力は重複する数字2または3である.
長さnの配列のすべての数字は0からn-1の範囲内にある.配列のいくつかの数字は重複していますが、いくつかの数字が重複していることは分かりません.数字ごとに何回繰り返されるか分からない.配列のいずれかの重複する数字を見つけてください.例えば、長さ7の配列{2,3,1,0,2,5,3}を入力すると、対応する出力は重複する数字2または3である.
public class duplicate {
// , ,
public static void duplicate(int[] numbers, int length, int[] duplication) {
boolean[] k = new boolean[length];
for (int i = 0; i < length; i++) {
if (k[numbers[i]] == true) {
duplication[0] = numbers[i];
System.out.println(numbers[i]);
}
k[numbers[i]] = true;
}
}
// , , , ,
public static boolean duplication(int[] numbers, int length, int[] duplication) {
if (numbers == null || length <= 0) {
return false;
}
for (int i = 0; i < length; i++) {
if (numbers[i] < 0 || numbers[i] >= length) {
return false;
}
}
for (int i = 0; i < length; i++) {
while (numbers[i] != i) {
if (numbers[i] == numbers[numbers[i]]) {
duplication[0] = numbers[i];
return true;
}
int temp = numbers[i];
numbers[i] = numbers[temp];
numbers[temp] = temp;
}
}
return false;
}
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int[] numbers = {2, 3, 1, 0, 2, 5, 3};
int[] a = new int[2];
duplicate(numbers, 7, a);
System.out.print(duplication(numbers, 7, a));
}
}