C++ simple solution leveraging the highest bit


  • 4
    Q
    /*
      The solution is based on the fact that all the input number are signed int, and
      given the condition that each number is larger than 0, we can leverage the highest
      bit in each number to store the information whether the number has been found already.
      If yes, just add the number in the vector to return, if not, we set the number's highest bit.
    */
    vector<int> findDuplicates(vector<int>& nums) {
    	vector<int> r;
    	for (int i = 0; i < nums.size(); ++i) {
    		int index = nums[i] & 0x7fffffff;
    		if (nums[index - 1] < 0) {
    			r.push_back(index);
    		}
    		else {
    			nums[index - 1] |= 0x80000000;
    		}
    	}
    	return r;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.