知识点：
排序一个长度为n的数组需要的时间变量和属性的区别：
变量是方法体中定义的，我们称为临时变量；属性是类体中定义的。权限标示符只用于修饰属性和方法。不修饰变量。方法中定义的临时变量在方法调用完成之后就不存在了，不需要用修饰符定义！
注意：
写代码之前，先将输入的范围固定
代码实现：
先将数组排序，比对数组前后的数值是否相同
/**
* 题1：找出数组中重复的数字
* 方法1：先排序；再比对数组前后的数值是否相同
*/
private static boolean findNum1(int[] ars) {
//将a数组排序
Arrays.sort(ars);
//比对数组中前后的数是否相同
for(int i=0; i<ars.length-1; i++) {
if(ars[i]==ars[i+1]) {
return true;
}
}
return false;
}
先判断数组下标i与对应数组的值arr[i]是否相同；若相同继续判断下一位；若不同，先判断arr[i]与arr[arr[i]]是否相同，若不同，交换位置，至arr[i]与i相同
/**
* 方法2：先判断ars下标i与ars[i]是否相同；
* 若不同，进行交换；
* 交换之前，判断交换的2数是否相同；
*/
private static boolean findNum2(int[] ars) {
if(ars==null||ars.length<=0) {
return false;
}
for(int i:ars) {
if(i<0||i>ars.length-1) {
return false;
}
}
for(int i=0;i<ars.length; i++) {
//如果i与ars[i]不等
while(ars[i]!=i) {
//判断是否相等
if(ars[i]==ars[ars[i]]) {
return true;
}
//进行交换
int tmp = ars[i];
ars[i] = ars[tmp];
ars[tmp] = tmp;
}
}
return false;
不修改数组找出重复数字—— 借助辅助数组
/**
* 题2不修改数组找出重复的数字
* 法1：复制至一个辅助数组，如原数组中被复制的数为2，则复制到下标为2的位置
*/
private static boolean findNum3(int[] ars) {
int [] newArray = new int[ars.length];
for(int i:ars) {
newArray[i]=-1;
}
for(int j=0; j<ars.length; j++) {
if(newArray[ars[j]]==ars[j]) {
return true;
}else {
newArray[ars[j]]=ars[j];
}
}
return false;
}
不修改数组找出重复数字—— 类二分查找
/**
* 题2不修改数组找出重复的数字
* 法2：二分查找法：先分两半，比较前一半数字的数目和与前一半数字的个数；
* 若大于，则说明有重复，在前一半数字中再进行分两半；若小于，则说明后一半有重复；
*/
private static int findNum4(int[] ars) {
if(ars==null||ars.length<=0) {
return -1;
}
int start=0;
int end=ars.length-1;
while(end>=start) {
//找中间数
int mid = (end - start)/2+start;
//比较前一部分数的个数和与前一部分的个数
int count = total(ars, start, mid);
//若迭代至一个数，且它的个数还大于1，输出这个数
if(start== end) {
if(count>1) {
System.out.println(start);
break;
}else {
break;
}
}
if(mid-start+1<count) {
end = mid;
}else {
start = mid+1;
}
}
return -1;
}
private static int total(int[] ars, int start, int end) {
int count =0;
for(int i=0; i<ars.length; i++) {
if(ars[i]>=start && ars[i]<=end) {
count++;
}
}
return count;
}
