lintcode 中等题:find the missing number 寻找缺失的数

题目

给出一个包含 0 .. N 中 N 个数的序列,找出0 .. N 中没有出现在序列中的那个数。

样例

N = 4 且序列为 [0, 1, 3] 时,缺失的数为2

注意

可以改变序列中数的位置。

挑战

在数组上原地完成,使用O(1)的额外空间和O(N)的时间。

解题

重新定义一个数组存放排序后的数,空间复杂度和时间复杂度都是O(N)

public class Solution {
    /**    
     * @param nums: an array of integers
     * @return: an integer
     */
    public int findMissing(int[] nums) {
        // write your code here
        boolean[] A = new boolean[nums.length +1];
        for(int i = 0;i<nums.length; i++){
            A[nums[i]] = true;
        }
        int n = 0;
        for(int i = 0;i< A.length ;i++){
            if(A[i] == false){
                n = i;
                break;
            }
        }
        
        return n;
    }
}
Java Code

总耗时: 1674 ms

class Solution:
    # @param nums: a list of integers
    # @return: an integer
    def findMissing(self, nums):
        # write your code here
        A = [False]*(len(nums) + 1)
        for a in nums:
            A[a] = True
        for i in range(len(A)):
            if A[i] == False:
                return i
Python Code

总耗时: 276 ms

在下面的挑战中,说可以在原始数组上面操作,如何在原始数组上面操作?空间复杂度并且是O(1) 

 i^i = 0 一个数自身的异或等于0

这个可以空间复杂可以是O(1),就有下面的代码了

public class Solution {
    /**    
     * @param nums: an array of integers
     * @return: an integer
     */
    public int findMissing(int[] nums) {
        // write your code here
        int res = 0;
        for( int i =0;i< nums.length ;i++){
            res = res ^ nums[i] ^ i;
        }
        res = res^(nums.length);
        return res;
    }
}
Java Code

总耗时: 1802 ms

class Solution:
    # @param nums: a list of integers
    # @return: an integer
    def findMissing(self, nums):
        # write your code here
        res = 0
        for i in range(len(nums)):
            res = res ^ i ^ nums[i]
        res ^= len(nums)
        return res 
Python Code

总耗时: 297 ms

书影博客中看到通过求和来找缺失的数,我都被这个机智的方法吓到了,竟然如此如此的机智

直接复制其代码:

class Solution(object):
    def missingNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        return n * (n + 1) / 2 - sum(nums)

 看到一个很牛逼的方法

在原始数组上,把A[i] 调整到其原来的位置 是的A[i] = i ,结束的地方就是当A[i] <0 此题目没有负数也没有影响的,A[i]>=n 显然的A[n]越界了。

以下面例子进行解释
[9,8,7,6,2,0,1,5,4],是长度为9的数组,按照题目的要求应该是0到9十个数字,找出缺失的那一个。
第0下标,9>=9 不做交换,下面的输出是只对交换的情况,在输出当前交换前和交换后的情况 ,黄色标记是交换的两个元素
第1下标,A[1]!=1 A[1]与A[A[1]]进行交换,即 8 4交换
before: [9, 8, 7, 6, 2, 0, 1, 5, 4] later: [9, 4, 7, 6, 2, 0, 1, 5, 8]
交换后的A[1]依旧不等于1,继续A[1]与A[A[1]]交换,即 4 2 交换 before: [9, 4, 7, 6, 2, 0, 1, 5, 8] later: [9, 2, 7, 6, 4, 0, 1, 5, 8]
2 7 进行交换 before: [9, 2, 7, 6, 4, 0, 1, 5, 8] later: [9, 7, 2, 6, 4, 0, 1, 5, 8]
7 5 进行交换 before: [9, 7, 2, 6, 4, 0, 1, 5, 8] later: [9, 5, 2, 6, 4, 0, 1, 7, 8]
5 0 进行交换 before: [9, 5, 2, 6, 4, 0, 1, 7, 8] later: [9, 0, 2, 6, 4, 5, 1, 7, 8]
9 0 进行交换 before: [9, 0, 2, 6, 4, 5, 1, 7, 8] later: [0, 9, 2, 6, 4, 5, 1, 7, 8]
此时A[1]>=n 不进行交换
第2下标,A[2]=2不进行交换
第3下标,A[3]!=3,6 1 进行交换 before: [0, 9, 2, 6, 4, 5, 1, 7, 8] later: [0, 9, 2, 1, 4, 5, 6, 7, 8]
1 9 进行交换 before: [0, 9, 2, 1, 4, 5, 6, 7, 8] later: [0, 1, 2, 9, 4, 5, 6, 7, 8]
以后的下标都和其元素值相等,不需要交换

下面只需要遍历数组,找出下标和值不相等的点即可,当都满足的时候,说明是n值不在数组中
说明下,中间有个缺失的数,那么一定有个其他数字占据了他的位置,找到这个位置就是答案了。
可以看出在一次交换时候,至少把一个元素调整到其所在的下标位置,也就是A[tmp] = tmp 这个元素 ,而A[i] = A[tmp]之前的元素的值,不能保证每次都使得自己的元素回到自己的位置,所以要用while多次循环。

如下,好好体会:

public class Solution {
    /**    
     * @param A: an array of integers
     * @return: an integer
     */
    public int findMissing(int[] A) {
        // write your code here
        int n = A.length;
        for(int i = 0;i< n;i++){
            
            while( A[i] != i){
                if(A[i] <0 || A[i] >= n)
                    break;
                int tmp = A[i];
                A[i] = A[tmp];
                A[tmp] = tmp;
            }
        }
        for(int i =0;i <n;i++){
            if(A[i] !=i)
                return i;
        }
        return n;
    }
}

 总耗时: 2141 ms

class Solution:
    # @param A: a list of integers
    # @return: an integer
    def findMissing(self, A):
        # write your code here
        n = len(A)
        if A == None or n == 0:
            return 0
        # num0 = A
        for i in range(n):
            while A[i] != i:
                # num0 = A[:]
                if A[i]<0 or A[i]>=n:
                    break
                tmp = A[i]
                A[i] = A[tmp]
                A[tmp] = tmp
                # if n > 6:
                    # print 'before:',num0
                    # print ' later:',A
                 
        for i in range(n):
            if A[i]!=i:
                return i
        return n
Python Code

总耗时: 352 ms

原文地址:https://www.cnblogs.com/theskulls/p/4943680.html