二维数组中的查找
- 在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中第一个重复的数字。 例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是第一个重复的数字2。没有重复的数字返回-1。
- 输入
[2,3,1,0,2,5,3]
- 返回值
2
书上答案为错，6320250,需要返回2，实际返回0
int duplicate(vector<int>& numbers) {
// write code here
int len=numbers.size();
for(int i=0;i<len;i++)
{
while(numbers[i]!=i)
{
if(numbers[i]==numbers[numbers[i]])
return numbers[i];
int t=numbers[i];
numbers[i]=numbers[t];
numbers[t]=t;
}
}
return -1;
}
大雪菜的也一样
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param numbers int整型vector
* @return int整型
*/
int duplicate(vector<int>& nums) {
int n=nums.size();
for(auto x:nums)
if(x<0||x>=n)
return -1;
for(int i=0;i<n;i++)
{
while(nums[i]!=i&&nums[nums[i]]!=nums[i])
swap(nums[i],nums[nums[i]]);
if(nums[i]!=i &&nums[i]==nums[nums[i]])
return nums[i];
}
return -1;
}
};
个人完美答案
int duplicate(vector<int>& numbers) {
int length=numbers.size();
for (int i = 0; i < length; i++)
{
int index = numbers[i];
if (index >= length)
{
index -= length;
}
if (numbers[index] >= length)
{
return index;
}
numbers[index] = numbers[index] + length;
}
return -1;
}class Solution
{
public:
bool duplicate(int numbers[], int length, int* duplication)
{
if(numbers==nullptr||length<=0)
{
return false;
}
for(int i=0;i<length;i++)
{
if(numbers[i]<0||numbers[i]>length-1)
return false;
}
for(int i=0;i<length;i++)
{
while(numbers[i]!=i)
{
if(numbers[i]==numbers[numbers[i]])
{
*duplication=numbers[i];
return true;
}
int t=numbers[i];
numbers[i]=numbers[t];
numbers[t]=t;
}
}
return false;
}
};
class Solution {
public:
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
bool duplicate(int numbers[], int length, int* duplication) {
vector<bool> f(length, false);
for (int i=0; i<length; ++i) {
if (!f[numbers[i]]) {
f[numbers[i]] = true;
}
else {
*duplication = numbers[i];
return true;
}
}
return false;
}
};
class Solution {
public:
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
bool duplicate(int numbers[], int length, int* duplication)
{
vector<bool> flag(length,false);
for(int i=0;i<length;i++)
{
if(flag[numbers[i]]==true)
{
*duplication=numbers[i];
return true;
}
else flag[numbers[i]]=true;
}
return false;
}
};
class Solution {
public:
bool duplicate(int numbers[], int length, int* duplication) {
if (length <= 0 || numbers == nullptr) {
return false;
}
for (int i = 0; i < length; i++) {
int index = numbers[i];
if (index >= length) {
index -= length;
}
if (numbers[index] >= length) {
duplication[0] = index;
return true;
}
numbers[index] += length;
}
return false;
}
};
class Solution {
public:
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
bool duplicate(int numbers[], int length, int* duplication) {
set<int> s;
bool flag = false ;
for(int i=0;i<length;i++){
int siz1 = s.size();
s.insert(numbers[i]);
int siz2 = s.size();
if(siz1 == siz2){
duplication[0] = numbers[i];
flag = true;
break ;
}
}
return flag ;
}
};
class Solution
{
public:
bool duplicate(int numbers[], int length, int *duplication)
{
for(int i=0;i<length-1;i++)
{
for(int j=i+1;j<length;j++)
{
if(numbers[i]==numbers[j])
{
*duplication=numbers[i];
return true;
}
}
}
return false;
}
};
#include <stdio.h>
#include <iostream>
using namespace std;
int countRange(const int *numbers, int length, int start, int end)
{
if (numbers == NULL)
return 0;
int count = 0;
for (int i = 0; i < length; i++)
{
if (numbers[i] >= start && numbers[i] <= end)
{
++count;
}
}
return count;
}
int getDuplication(const int *numbers, int length)
{
if (length <= 0)
return -1;
int start = 1;
int end = length - 1;
while (end >= start)
{
int middle = (start + end) / 2;
int count = countRange(numbers, length, start, middle);
if (end == start)
{
if (count > 1)
return start;
else
break;
}
if (count > (middle - start + 1))
end = middle;
else
start = middle + 1;
}
return -1;
}
int main()
{
int a[10] = {2, 3, 5, 4, 3, 2, 6, 7};
cout << getDuplication(a, 8);
}
#include <stdio.h>
#include <iostream>
using namespace std;
int getDuplication(const int *numbers, int length)
{
if (length <= 0)
return -1;
int start = 1;
int end = length - 1;
while (end >= start)
{
int middle = (start + end) / 2;
int count = 0;
for(int j=0;j<length;j++)
{
if(numbers[j]>=start&&numbers[j]<=middle)
count++;
}
if (end == start)
{
if (count > 1)
return start;
else
break;
}
if (count > (middle - start + 1))
end = middle;
else
start = middle + 1;
}
return -1;
}
int main()
{
int a[8] = {2, 3, 5, 4, 3, 2, 6, 7};
cout << getDuplication(a,8);
}
