[LintCode] Find the Missing Number [三种方法]

liaoyg8023 发布于2019-08-14 15:20 / 2590人阅读

摘要：求和相减是先求出到这个等差数列的和，再减去实际数组的和，就是缺失的数，第二种方法是，只要先按顺序排列好，用二分法找到第一个和不相等的数就可以了。二分法求和相减法共个数，多加了一个异或法

Problem

Given an array contains N numbers of 0 .. N, find which number doesn"t exist in the array.

Example

Given N = 3 and the array [0, 1, 3], return 2.

Note

找第一个缺失的数，可以用求和相减或二分法查找，也可以用位运算XOR来做。
求和相减是先求出0到N这个等差数列的和，再减去实际数组的和，就是缺失的数，
第二种方法是，只要先按顺序排列好[0, 1, 2, 3, 4, ...]，用二分法找到第一个和A[i]不相等的数i就可以了。

Solution

1. 二分法

public class Solution {
    public int findMissing(int[] A) {
        int len = A.length;
        Arrays.sort(A);
        int left = 0, right = len - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (A[mid] > mid) {
                right = mid - 1;
            }
            else {
                left = mid + 1;
            }
        }
        return A[left] == left ? left + 1 : left;
    }
}

2. 求和相减法

public class Solution {
    public int findMissing(int[] A) {
        int len = A.length;
        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += A[i];
        }
        int targetsum = len * (len + 1) / 2; //0, 1, 2,...,len, 共len+1个数，多加了一个len
        return targetsum - sum;
    }
}

3. 异或法

public class Solution {
    public int findMissing(int[] nums) {
        int x = 0;
        for (int i = 0; i <= nums.length; i++) {
            x ^= i;
        }
        for (int i = 0; i < nums.length; i++) {
            x ^= nums[i];
        }
        return x;
    }
}

GPU云服务器云服务器三种实现方法三种画线方法java LintCode the

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/65628.html

[LintCode/LeetCode] Set Mismatch

Problem The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetit...

Astrian 2019-08-16 12:45 评论0 收藏0
[LintCode] Missing String

Problem Given two strings, you have to find the missing string. Example Given a string str1 = This is an exampleGiven another string str2 = is example Return [This, an] Solution public class Solution ...

IamDLY 2019-08-16 11:02 评论0 收藏0
[LintCode] First Missing Positive

摘要：找第一个缺失的正整数，只要先按顺序排列好，也就是，找到第一个和不对应的数就可以了。注意数组的从开始，而正整数从开始，所以重写排列的时候要注意换成，而就是从开始的数组中的元素。 Problem Given an unsorted integer array, find the first missing positive integer. Example Given [1,2,0] re...

snifes 2019-08-14 15:20 评论0 收藏0
[LeetCode/LintCode] Number of Islands [DFS]

摘要：两个循环遍历整个矩阵，出现则将其周围相邻的全部标记为，用子函数递归标记。注意里每次递归都要判断边界。写一个的，写熟练。 Number of Islands Problem Given a boolean/char 2D matrix, find the number of islands. 0 is represented as the sea, 1 is represented as...

Fourierr 2019-08-14 15:15 评论0 收藏0
[LintCode/LeetCode] Find Median From / Data Stream

摘要：建立两个堆，一个堆就是本身，也就是一个最小堆另一个要写一个，使之成为一个最大堆。我们把遍历过的数组元素对半分到两个堆里，更大的数放在最小堆，较小的数放在最大堆。同时，确保最大堆的比最小堆大，才能从最大堆的顶端返回。 Problem Numbers keep coming, return the median of numbers at every time a new number a...

zxhaaa 2019-08-14 14:35 评论0 收藏0