Problems using algorithm related to graph while the statement does not mention graph

wei zhang
wei zhang
Aug 23, 2017 · 2 min read

One example is

Find the Duplicate Number

One quick solution is like this:

class Solution {
public:
/**
* @param nums an array containing n + 1 integers which is between 1 and n
* @return the duplicate one
*/

int findDuplicate(vector<int>& nums) {
int slow = 0;
int fast = 0;

do {
slow = nums[slow];
fast = nums[fast];
fast = nums[fast];
} while((slow != fast) )
;
fast = 0;

while(slow != fast) {
slow = nums[slow];
fast = nums[fast];
}

return(slow);




}
int findDuplicate1(vector<int>& nums) {
// Write your code here
int n = nums.size() - 1;
int left = 1, right = n, mid;
//cout<<n<<endl;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
//cout<< left <<" " <<mid<<" " <<right<<endl;
if (count_less_or_equal(nums, mid) <= mid) {
left = mid;
} else if (count_larger(nums, mid) <= n - mid){
right = mid;
}

}
//cout<< left <<" " <<right<<endl;
if (count_equal(nums, left) >= 2) {
return(left);
} else {
return(right);
}
}
int count_less_or_equal(vector<int>&nums, int p) {
int res = 0;
for (auto i : nums) {
if (i <= p) {
res++;
}
}
//cout<<"less"<<res<<endl;
return(res);
}

int count_equal(vector<int>&nums, int p) {
int res = 0;
for (auto i : nums) {
if (i == p) {
res++;
}
}
//cout<<"=="<<res<<endl;
return(res);
}

int count_larger(vector<int>&nums, int p) {
int res = 0;
for (auto i : nums) {
if (i > p) {
res++;
}
}
//cout<<"larger"<<res<<endl;
return(res);
}
};

So, why do we have the first quick method?

Think about the case we have n distinct number in A[i] with values from 0 to n-1, then if we have node with index i, and add node i an edge from i pointing to A[i]. as all node have in degree 1 and out degree 1, then the graph are actually 1 or more circles. If we construct the graph when we have n +1 values, and the values are chosen from 1 to n, we do still have circles, but the node 0 have in degree 0 as there is no point going to 0, so the branch which 0 is located must have another node with in degree 2 ore more, which corresponds to the duplicated number, we know this special branch have at least one loop, so we can use the finding loop algorithm to find the starting point of the loop. What if we have n +1 problems, and the values are choosed from 0 to n -1?

To be added

)
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade