Swapping numbers to the same index cell


  • 22
    L

    1.swapping number solution

    public int MissingNumber(int[] nums) {
        for(int i = 0; i < nums.Length; i++)
        {
            while(i < nums.Length && nums[i] == i) i++;
            while(i < nums.Length && nums[i] != i)
            {
                if(nums[i] >= nums.Length || nums[i] < 0) break;
                nums[i] = nums[i] ^ nums[nums[i]] ^ (nums[nums[i]] = nums[i]);
            }
        }
        for(int i = 0; i < nums.Length; i++)
            if(nums[i] != i) return i;
        return nums.Length;
    }
    

    1.2 Another swapping solution by avoiding the 2nd loop. Idea from novostary.

    public int MissingNumber(int[] nums) {
        int lastIndex = nums.Length;
        for(int i = 0; i < nums.Length; )
            if(nums[i] == i) i++;
            else if(nums[i] < nums.Length)
                nums[i] = nums[i] ^ nums[nums[i]] ^ (nums[nums[i]] = nums[i]);
            else lastIndex = i++;
        return lastIndex;
    }
    

    2.Bitwise operation solution

    public int MissingNumber(int[] nums) {
        int xorResult = 0;
        for(int i = 0; i < nums.Length; i++)
            xorResult ^= nums[i] ^ i;
        xorResult ^= nums.Length;
        return xorResult;
    }
    

    3.Math solution by sum total

    public int MissingNumber(int[] nums) {
        int result = nums.Length * (nums.Length + 1) / 2;
        for(int i = 0; i < nums.Length; i++)
            result -= nums[i];
        return result;
    }

  • 3
    N

    Maybe we can record the position when nums[cur] == size. And the last position is our result if this condition occurs.

    Sorry for that I use C++.

    int missingNumber(vector<int>& nums) { // Runtime: 36 ms
        int cur = 0, pre = -1, size = nums.size();
        while (cur < size) {
            if (nums[cur] != cur) {
                if (nums[cur] != size) {
                    swap(nums[cur], nums[nums[cur]]);
                } else {
                    pre = cur;
                    cur++;
                }
            } else {
                cur++;
            }
        }
        return pre == -1 ? size : pre;
    }

  • 0
    L

    Understood. This saves another O(n) loop. Great and thanks.


Log in to reply
 

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