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

liaoyg8023 發布于2019-08-14 15:20 / 2608人閱讀

摘要：求和相減是先求出到這個等差數列的和，再減去實際數組的和，就是缺失的數，第二種方法是，只要先按順序排列好，用二分法找到第一個和不相等的數就可以了。二分法求和相減法共個數，多加了一個異或法

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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