[C++] Solution O(1) space O(N) time


  • 0
    /**
     * For every number num, if it is not in the right seat, send it home, mark the seat as empty by 0;
     * If its seat is occupied by another number other, send the other home;
     * If its seat is occupied by a same number, it is duplicate.
     * scan the array for 0, means empty seat;
     */
    class Solution {
    public:
        vector<int> findErrorNums(vector<int>& a) {
            vector<int> res(2);
            int n = a.size();
            for (int i = 0; i < n; i++) {
                if (a[i] != i + 1 && a[i] != 0) {
                    int j = i;
                    int k = a[j];
                    a[j] = 0;
                    while (k != j + 1) {
                        j = k - 1;
                        // dup
                        if (a[j] == 0) {
                            a[j] = k;
                        }
                        else if (a[k - 1] == k) {
                            res[0] = k;
                        }
                        else {
                            int other = a[j];
                            a[j] = k;
                            k = other;
                        }
                    }
                }
            }
    
            // scan the array for 0, means empty seat;
            for (int i = 0; i < n; i++) {
                if (a[i] == 0) {
                    res[1] = i + 1;
                    break;
                }
            }
            
            return res;
        }
    };
    

  • 0

Log in to reply
 

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