
问题
给定一个包含 0, 1, 2, ..., n
中 n 个数的序列,找出 0 .. n 中没有出现在序列中的那个数。
输入: [3,0,1]
输出: 2
输入: [9,6,4,2,3,5,7,0,1]
输出: 8
说明:
你的算法应具有线性时间复杂度。你能否仅使用额外常数空间来实现?
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n
, find the one that is missing from the array.
Input: [3,0,1]
Output: 2
Input: [9,6,4,2,3,5,7,0,1]
Output: 8
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
示例
public class Program { public static void Main(string[] args) { int[] nums = null; nums = new int[] { 9, 6, 4, 2, 3, 5, 7, 0, 1 }; var res = MissingNumber(nums); Console.WriteLine(res); res = MissingNumber2(nums); Console.WriteLine(res); Console.ReadKey(); } private static int MissingNumber(int[] nums) { //求和法 if(!nums.Contains(0)) return 0; var sum = 0; foreach(var num in nums) { sum += num; } int max = nums.Length; return (1 + max) * max / 2 - sum; } private static int MissingNumber2(int[] nums) { //异或法 //异或满足交换律,我们有以下公式 //A ^ B = B ^ A //(A ^ B) ^ C = A ^ (B ^ C) //A ^ C ^ B ^ A ^ C = A ^ A ^ C ^ C ^ B = B //对于数组 [2, 3, 4, 0] //res初始值为 0 //异或 0 ^ (2 ^ 1) ^ (3 ^ 2) ^ (4 ^ 3) ^ (0 ^ 4) //= (0 ^ 0) ^ (1) ^ (2 ^ 2) ^ (3 ^ 3) ^ (4 ^ 4) = 1 int res = 0; for(int i = 0; i < nums.Length; i++) res ^= nums[i] ^ (i + 1); return res; } }
以上给出2种算法实现,以下是这个案例的输出结果:
8 8
分析:
显而易见,2种算法的时间复杂度均为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/4056。