摘要:題目解答一開始我的思始很簡(jiǎn)單,排序,查找但是可以用的方法,因?yàn)橹挥幸粋€(gè),所以可以把其它所有的數(shù)都配好對(duì),剩下這個(gè)就是我們要找的這里很喔,因?yàn)橹簧倭艘粋€(gè)數(shù),舉個(gè)例子所以當(dāng)我們把這些數(shù)的時(shí)候,唯一一個(gè)剩下的就是的這個(gè)數(shù)
題目:
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?
解答:
一開始我的思始很簡(jiǎn)單,排序,查找:
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方法,因?yàn)橹挥幸粋€(gè)missing number,所以可以把其它所有的數(shù)都配好對(duì),剩下這個(gè)就是我們要找的number:
public int missingNumber(int[] nums) { int xor = 0, i = 0; //這里很triky喔,因?yàn)橹簧倭艘粋€(gè)數(shù),舉個(gè)例子: //nums: 1, 3, 4 // i: 1, 2, 3, (4) //所以當(dāng)我們把這些數(shù)xor的時(shí)候,唯一一個(gè)剩下的就是2, missing的這個(gè)數(shù) for (i = 0; i < nums.length; i++) { xor = xor ^ i ^ nums[i]; } return xor ^ i; }
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/64929.html
摘要:之后我們可以查看頭尾兩個(gè)數(shù)字是否符合要求。如果不符合我們可以直接返回結(jié)果。方法利用的特點(diǎn)。方法求和根據(jù)高斯定理,從到的和為。所以把數(shù)組的所有數(shù)字求和,然后與從到的和相減所得數(shù)字,就是我們需要的數(shù)字。 題目鏈接:Missing Number 思路:方法1: 排序我們很自然的可以想到,如果數(shù)組是排好序的,那么可以很容易的找到缺少的數(shù)字。之后我們可以查看頭尾兩個(gè)數(shù)字是否符合要求。如果不符合我...
摘要:題目詳情題目的意思是輸入一個(gè)長度為的數(shù)組,找到這個(gè)數(shù)字中不存在于數(shù)組中的丟失的數(shù)字思路我的想法是,用這個(gè)數(shù)的和減去數(shù)組中的每一個(gè)元素的值,最后剩下的值就是丟失的數(shù)字解法 題目詳情 Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing fr...
摘要:前言從開始寫相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)懍F(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個(gè)索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新 前言 從開始寫leetcode相關(guān)的博客到現(xiàn)在也蠻多篇了。而且當(dāng)時(shí)也沒有按順序?qū)憽F(xiàn)在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個(gè)索引嘻嘻。 順序整理 1~50 1...
摘要:題目描述給定一個(gè)包含中個(gè)數(shù)的序列,找出中沒有出現(xiàn)在序列中的那個(gè)數(shù)。示例輸入輸出示例輸入輸出最簡(jiǎn)單的解法剛看到的這道題的時(shí)候,第一感覺就是排序,之后直接挨個(gè)比較就能找到缺失的數(shù)字。 題目描述 給定一個(gè)包含 0, 1, 2, ..., n 中 n 個(gè)數(shù)的序列,找出 0 .. n 中沒有出現(xiàn)在序列中的那個(gè)數(shù)。 示例 1: 輸入: [3,0,1] 輸出: 2 示例 2: 輸入: [9,6,...
摘要:在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起,每天更新一題,順序從易到難,目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目,語言 JavaScript。 在線網(wǎng)站:https://cattle.w3fun.com GitHub 地址:https://github.com/swpuLeo/ca...我的微信公眾號(hào): showImg(htt...
閱讀 1033·2021-11-25 09:43
閱讀 1413·2021-11-18 10:02
閱讀 1814·2021-11-02 14:41
閱讀 2366·2019-08-30 15:55
閱讀 1068·2019-08-29 16:18
閱讀 2553·2019-08-29 14:15
閱讀 1391·2019-08-26 18:13
閱讀 733·2019-08-26 10:27