Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive),
- prove that at least one duplicate number must exist. Assume that there is only one duplicate number,
- find the duplicate one.
- Example 1:
- ----------
- Input: [1,3,4,2,2]
- Output: 2
- Example 2:
- ----------
- Input: [3,1,3,4,2]
- Output: 3
- Note:
- -----
- 1. You must not modify the array (assume the array is read only).
- 2. You must use only constant, O(1) extra space.
- 3. Your runtime complexity should be less than O(n2).
- 4. There is only one duplicate number in the array, but it could be repeated more than once.
- */
- namespace CsharpSolutions.Problems.LeetCode.Array.FindTheDuplicateNumber_287
- {
- public class Solution
- {
- /// <summary>
- /// Finds duplicate in an array of integers.
- /// Uses Floyds Tortoise and Hare Algorithm.
- /// Time complexity : O(n)
- /// Space complexity : O(1)
- /// </summary>
- /// <param name="nums">An array of integers.</param>
- public int FindDuplicate(int[] nums)
- {
- var tortoise = nums[nums[0]];
- var hare = nums[nums[nums[0]]];
- while (tortoise != hare)
- {
- tortoise = nums[tortoise];
- hare = nums[nums[hare]];
- }
- hare = nums[0];
- while (tortoise != hare)
- {
- tortoise = nums[tortoise];
- hare = nums[hare];
- }
- return hare;
- }
- /// <summary>
- /// Finds duplicate in an array of integers.
- /// Uses HashSet to record previously seen integers.
- /// Time complexity : O(n)
- /// Space complexity : O(n)
- /// </summary>
- /// <param name="nums">An array of integers.</param>
- public int FindDuplicate2(int[] nums)
- {
- var seenIntegers = new System.Collections.Generic.HashSet<int>();
- foreach (var num in nums)
- {
- if (seenIntegers.Contains(num))
- return num;
- seenIntegers.Add(num);
- }
- return -1;
- }
- /// <summary>
- /// Finds duplicate in an array of integers.
- /// Sorts the array first, then applies linear search.
- /// Time complexity : O(nlgn)
- /// Space complexity : If source is mutable, O(1) / Otherwise, O(n)
- /// </summary>
- /// <param name="nums">An array of integers.</param>
- public int FindDuplicate3(int[] nums)
- {
- System.Array.Sort(nums);
- for (var i = 1; i < nums.Length; i++)
- if (nums[i] == nums[i - 1])
- return nums[i];
- return -1;
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement