方案一:
Java代码:
class Solution {
public int duplicateInArray(int[] nums) {
// 如果输入数组是空, 直接返回-1
if (nums.length == 0) return -1;
// 创建aa数组, 长度是 n
int aa[] = new int[nums.length];
for (int i = 0; i<nums.length; i++){
if (nums[i] < 0 || nums[i] > (nums.length-1)) return -1;
aa[nums[i]] ++;
}
for (int i=0; i<nums.length; i++){
if (aa[i] > 1) return i;
}
return -1;
}
}
解题思路:
因为输入的是数组, 并且数组中元素在 0-n-1之间,
因此直接设 一个新的数组 aa, 长度为n, 这样nums数组中的元素大小对应于 aa数组的索引,
当 nums 中出现该元素, 对应aa数组的索引位置+1,
最后遍历 aa 数组, 当值大于2时, 说明该索引在 nums 数组中出现的次数多于1次, 返回 索引值
需要注意:
输入数组是空, 直接返回 -1
nums中的数组元素 不满足 [0, n-1] 的条件, 直接返回-1
方案二:
Java代码
class Solution {
public int duplicateInArray(int[] nums) {
// 方法2:
int n = nums.length;
if (n==0) return -1;
// 进行数组扫描
for (int i=0; i<n; i++){
// 如果 nums 数组中的元素不满足条件, 则返回-1
if (nums[i] < 0 || nums[i] > (n-1)) return -1;
}
for (int i=0; i<n; i++){
// 将nums数组中的每一个元素放入对应的索引中
while(nums[i] != nums[nums[i]]) {
// swap(nums[i], nums[nums[i]]);
// 进行交换
int x = nums[i];
// 将 每一个元素放入对应的索引中
nums[i] = nums[nums[i]];
nums[x] = x;
}
// 循环结束的情况:
// 1. nums[0]=0, 即第i个索引位置 正好是元素i, 则进入下一个for循环 i++
// 2. nums[0]=x, and nums[x] =x, 说明第x个索引位置正好是元素x, 并且因此 nums[0]=x, 说明x元素不止一个
if (nums[i] != i) return nums[i];
}
return -1;
}
}
解题思路
将 每一个元素nums[i] 放入到 对应的索引位置
当 索引为 nums[i] 的位置的元素不等于 nums[i], 则将其两者交换