```
class Solution {
public:
int findDuplicate(vector<int>& nums) {
sort(nums.begin(), nums.end());
for (int i = 0;i<nums.size();i++)
if (nums[i]==nums[i+1])
return nums[i];
}
};
```

This is my solution. Sort first, and then compare between num, once they are the same, answer is found.

It seems satisfy the request.

What's more, I don't understand the request that " Your runtime complexity should be less than O(n2)", I think its wrong? It should be O(nlgn)?