我的LeetCode：https://leetcode-cn.com/u/ituring/
我的LeetCode刷題原始碼[GitHub]：https://github.com/izhoujie/Algorithmcii
LeetCode 面試題53 - II. 0～n-1中缺失的數字
題目
一個長度為n-1的遞增排序陣列中的所有數字都是唯一的，并且每個數字都在范圍0～n-1之內，在范圍0～n-1內的n個數字中有且只有一個數字不在該陣列中，請找出這個數字，
示例 1:
輸入: [0,1,3]
輸出: 2
示例 2:
輸入: [0,1,2,3,4,5,6,7,9]
輸出: 8
限制：
- 1 <= 陣列長度 <= 10000
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
解題思路
思路1-利用異或
因為所有的數都在0~n-1之間；
那么用0與所有的[i]以及i異或，最后再與n異或即可獲得缺失的數；
演算法復雜度:
- 時間復雜度： $ {\color{Magenta}{\Omicron\left(n\right)}} $
- 空間復雜度： $ {\color{Magenta}{\Omicron\left(1\right)}} $
演算法原始碼示例
package leetcode;
/**
* @author ZhouJie
* @date 2020年5月17日 上午12:51:33
* @Description: 面試題53 - II. 0～n-1中缺失的數字
*
*/
public class LeetCode_Offer_53_2 {
}
class Solution_Offer_53_2 {
/**
* @author: ZhouJie
* @date: 2020年5月17日 上午12:51:59
* @param: @param nums
* @param: @return
* @return: int
* @Description: 1-利用異或的特性；
*
*/
public int missingNumber(int[] nums) {
int number = nums.length;
for (int i = 0; i < nums.length; i++) {
number ^= nums[i] ^ i;
}
return number;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/189842.html
標籤：Java