Missing Related Problem Set


  • 0
    F

    Find the Duplicate Number
    Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

    Solution 1:

    class Solution {
    public:
        int findDuplicate(vector<int>& nums) {
            int low = 1;
            int high = nums.size();
            int mid = 0, count = 0;
            while (low < high) {
                mid = (low + high) / 2;
                count = 0;
                for(auto num : nums) 
                    if (num <= mid)  count++;
                if (count <= mid)
                    low = mid + 1;
                else 
                    high = mid;
            }
            return low;
        }
    };
    

    Detect cycle start point Method

    class Solution {
    public:
        int findDuplicate(vector<int>& nums) {
            if (nums.size() > 1) {
                int slow = nums[0];
                int fast = nums[nums[0]];
                while (slow != fast) {
                    slow = nums[slow];
                    fast = nums[nums[fast]];
                }
                fast = 0;
                while (fast != slow) {
                    fast = nums[fast];
                    slow = nums[slow];
                }
                return slow;
            }
            return -1;
        }
    };
    

    Missing Number

    Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

    class Solution {
    public:
        int missingNumber(vector<int>& nums) {
            //[left, right)
            int left = 0, right = nums.size();
            int cnt = 0;
            while (left < right) {
                int mid = left + (right-left)/2;
                cnt = 0;
                for (auto num : nums) {
                    if (num <= mid) cnt++;
                }
                if (cnt == (mid+1)) left = mid + 1;
                else right = mid;
            }
            return left;
        }
    };
    

    Find first missing number Positive Number

    class Solution {
    public:
        int firstMissingPositive(vector<int>& nums) {
            int n = nums.size();
            for (int i = 0; i < n; i++) 
                while (nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i]) 
                    swap(nums[i], nums[nums[i]-1]);
            for (int i = 0; i < n; i++) {
                if (nums[i] != i + 1)
                    return i + 1;
            }
            return n + 1;
        }
    };
    

    Missing Ranges

    Given a sorted integer array where the range of elements are [0, 99] inclusive, return its missing ranges.

    class Solution {
    	vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
    		vector<string> ranges;
    		int next = lower;
    		for (int i = 0; i < nums.size(); i++) {
    			if (nums[i] == next) {
    				next++;
    				continue;
    			}
    			ranges.push_back(get_range(next, nums[i]-1));
    			next = nums[i] + 1;
    		}
    		if (next <= upper) ranges.push_back(get_range(next, upper));
    		return ranges;
    	}
    
    	string get_range(const int lower, const int upper) {
    		if (lower == upper) {
    			return to_string(lower);
    		} else {
    			return to_string(lower) + "->" + to_string(upper);
    		}
    	}
    };
    

    There is another related problem , Summary Ranges

    class Solution {
    public:
        vector<string> summaryRanges(vector<int>& nums) {
            vector<string> result;
            int i = 0, n = nums.size();
            while (i < n) {
            	int j = 1;
            	while (i + j < n && nums[i+j]-nums[i] == j) ++j;
            	result.push_back(j <= 1 ? to_string(nums[i]) : to_string(nums[i]) + "->" + to_string(nums[i + j - 1]));
            	i += j;
            }
            return result;
        }
    };
    

Log in to reply
 

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