268. Missing Number

NSFish 發布于2019-08-14 14:18 / 1292人閱讀

摘要：題目解答一開始我的思始很簡單，排序，查找但是可以用的方法，因為只有一個，所以可以把其它所有的數都配好對，剩下這個就是我們要找的這里很喔，因為只少了一個數，舉個例子所以當我們把這些數的時候，唯一一個剩下的就是的這個數

題目：
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example,
Given nums = [0, 1, 3] return 2.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

解答：
一開始我的思始很簡單，排序，查找：

public int missingNumber(int[] nums) {
    if (nums == null || nums.length == 0) return 0;
    int result = 0;
    
    Arrays.sort(nums);
    for (int i = 0; i < nums.length; i++) {
        if (result != nums[i]) {
            return result;
        }
        result++;
    }
    return nums.length;
}

但是可以用xor的triky方法，因為只有一個missing number，所以可以把其它所有的數都配好對，剩下這個就是我們要找的number:

public int missingNumber(int[] nums) {
    int xor = 0, i = 0;
    
    //這里很triky喔，因為只少了一個數，舉個例子：
    //nums: 1, 3, 4
    //   i: 1, 2, 3, (4)
    //所以當我們把這些數xor的時候，唯一一個剩下的就是2, missing的這個數
    
    for (i = 0; i < nums.length; i++) {
        xor = xor ^ i ^ nums[i];
    }
    
    return xor ^ i;
}

GPU云服務器云服務器 missing method_missing aapt is missing number

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

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/64929.html

268. Missing Number

摘要：之后我們可以查看頭尾兩個數字是否符合要求。如果不符合我們可以直接返回結果。方法利用的特點。方法求和根據高斯定理，從到的和為。所以把數組的所有數字求和，然后與從到的和相減所得數字，就是我們需要的數字。題目鏈接：Missing Number 思路：方法1: 排序我們很自然的可以想到，如果數組是排好序的，那么可以很容易的找到缺少的數字。之后我們可以查看頭尾兩個數字是否符合要求。如果不符合我...

Steven 2019-07-30 17:01 評論0 收藏0
leetcode 268 Missing Number

摘要：題目詳情題目的意思是輸入一個長度為的數組，找到這個數字中不存在于數組中的丟失的數字思路我的想法是，用這個數的和減去數組中的每一個元素的值，最后剩下的值就是丟失的數字解法題目詳情 Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing fr...

tianyu 2019-08-15 13:54 評論0 收藏0
leetcode 部分解答索引（持續更新～）

摘要：前言從開始寫相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開始寫leetcode相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫～現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理 1~50 1...

leo108 2019-08-15 14:26 評論0 收藏0
LeetCode偶爾一題 —— 268. 缺失數字

摘要：題目描述給定一個包含中個數的序列，找出中沒有出現在序列中的那個數。示例輸入輸出示例輸入輸出最簡單的解法剛看到的這道題的時候，第一感覺就是排序，之后直接挨個比較就能找到缺失的數字。題目描述給定一個包含 0, 1, 2, ..., n 中 n 個數的序列，找出 0 .. n 中沒有出現在序列中的那個數。示例 1: 輸入: [3,0,1] 輸出: 2 示例 2: 輸入: [9,6,...

e10101 2019-08-26 10:22 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0