
问题
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?
输入: [2,2,1]
输出: 1
输入: [4,1,2,1,2]
输出: 4
Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Note:Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
Input: [2,2,1]
Output: 1
Input: [4,1,2,1,2]
Output: 4
示例
public class Program { public static void Main(string[] args) { int[] nums = null; nums = new int[] { 4, 1, 2, 1, 2 }; var res = SingleNumber(nums); Console.WriteLine(res); nums = new int[] { 2, 2, 1 }; res = SingleNumber2(nums); Console.WriteLine(res); nums = new int[] { 5, 9, 3, 9, 3, 2, 5 }; res = SingleNumber3(nums); Console.WriteLine(res); Console.ReadKey(); } private static int SingleNumber(int[] nums) { var dic = new Dictionary<int, int>(); for(var i = 0; i < nums.Length; i++) { if(dic.ContainsKey(nums[i])) { dic[nums[i]]++; } else { dic[nums[i]] = 0; } } foreach(var item in dic) { if(item.Value == 0) { return item.Key; } } return 0; } private static int SingleNumber2(int[] nums) { var table = new Hashtable(); for(var i = 0; i < nums.Length; i++) { if(table.ContainsKey(nums[i])) { table.Remove(nums[i]); } else { table.Add(nums[i], nums[i]); } } var enumerator = table.Values.GetEnumerator(); enumerator.MoveNext(); return (int)enumerator.Current; } private static int SingleNumber3(int[] nums) { var result = 0; foreach(var num in nums) { result ^= num; } return result; } }
以上给出3种算法实现,以下是这个案例的输出结果:
4 1 2
分析:
显而易见,以上3种算法的时间复杂度均为: 。SingleNumber3的执行效率是最高的,并且没有使用额外的空间,意思是指算法的空间复杂度为
。
SingleNumber3的解法分析参考我的另一篇博文 C#LeetCode刷题之#268-缺失数字(Missing Number)。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/4046。