-
Notifications
You must be signed in to change notification settings - Fork 0
/
Find Duplicate in Array
93 lines (62 loc) · 1.83 KB
/
Find Duplicate in Array
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
Given a read only array of n + 1 integers between 1 and n, find one number that repeats in linear time using less than O(n) space and traversing the stream sequentially O(1) times.
Sample Input:
[3 4 1 4 1]
Sample Output:
1
If there are multiple possible answers ( like in the sample case above ), output any one.
If there is no duplicate, output -1
//Solutions #1
_______________
int Solution::repeatedNumber(const vector<int> &nums) {
vector<int> arr;
arr = A;
for(int i =0;i<v.size();i++){
if(v[abs(v[i])]<=0)return abs(v[i]);
else{
v[abs(v[i])] = -v[abs(v[i])];
}
}
}
//Solutions #2
int Solution::repeatedNumber(const vector<int> &nums) {
set<int> s;
for(int i =0;i<A.size();i++){
if(s.end()== s.find(A[i])){
s.insert(A[i]);
}
else{
return (A[i]);
}
}
}
//Solution #3
int Solution::repeatedNumber(const vector<int> &nums) {
vector<int>*temp=(vector<int>*)&nums;
sort(temp->begin(),temp->end());
for(int i =0;i<nums.size();i++){
if(nums[i]==nums[i+1]){
return nums[i];
}
}
}
//Solution #4
int countNo(vector<int>& nums,int mid){
int count = 0;
for(auto k:nums){
if(k<=mid){
count++;
}
}
return count;
}
int Solution::repeatedNumber(const vector<int> &nums) {
int left = 0;
int right = nums.size();
while(left<right){
int mid = left+(right-left)/2;
int count = countNo(nums,mid);
if(count>mid) right = mid;
else left = mid+1;
}
return left;
}