classSolution{public:intfindDuplicate(vector<int>&nums){sort(nums.begin(),nums.end());intn=nums.size();for(inti=0;i<n-1;i++){if(nums[i]==nums[i+1])returnnums[i];}return-1;}};// Time Complexity: O(nlogn)// Space Complexity: O(n)

classSolution{public:intfindDuplicate(vector<int>&nums){constintMX=1e6+5;bitset<MX>mask;for(inti=0;i<nums.size();i++){if(mask[nums[i]]==1)returnnums[i];mask[nums[i]]=1;}return0;}};