My C++ Solution


  • 0
    Z
    class Solution {
    public:
        vector<int> findErrorNums(vector<int>& nums) {
            int len = nums.size(), ki = 0;
            stack<pair<int, int>> my_stk;
            my_stk.push(make_pair(0, len - 1));
            for(; my_stk.size(); ) {
                int f = my_stk.top().first,
                    front = f, 
                    rear = my_stk.top().second, 
                    r = rear,
                    key_val = nums[f];
                my_stk.pop();
                while(f < r) {
                    while(nums[r] >= key_val && f < r) {
                        --r;
                    }
                    nums[f] = nums[r];
                    while(nums[f] <= key_val && f < r) {
                        ++f;
                    }
                    nums[r] = nums[f];
                }
                nums[f] = key_val;
                if(f > 0 && nums[f - 1] == nums[f]) {
                    ki = f;
                    break;
                } else if(f < len - 1 && nums[f] == nums[f + 1]){
                    ki = ++f;
                    break;
                }
                else {
                    if(front < f)   my_stk.push(make_pair(front, f));
                    if(f + 1 < rear)    my_stk.push(make_pair(f + 1, rear));
                }
            }
            int begin, end, temp = nums[ki];
            if(nums[ki] == ki) {
                begin = ki, end = len;
            }
            else {
                begin = 0, end = ki;
            }
            for(int i = begin; i < end; ++i) {
                temp ^= nums[i] ^ (i + 1);
            }
            return vector<int>{nums[ki], temp};
        }
        
    };
    
    

Log in to reply
 

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