public class Solution {
public int findDuplicate(int[] nums) {
int i=0,index=0,r=1;
for(i=0;i<nums.length;i++){
index = Math.abs(nums[i])1;
if(nums[index]<0){
r= index+1;
break;
}
nums[index] = nums[index];
}
// restore
for(i=0;i<nums.length;i++){
nums[i]=Math.abs(nums[i]);
}
return r;
}
}
O(n) Time O(1)space,the simplest method



@halfopen Readonly doesn't mean you can write it to a different value then restore it to its original value.