Created
June 29, 2017 21:19
-
-
Save jianminchen/bbe19acd97462e3ed69ca507f7b9763f to your computer and use it in GitHub Desktop.
Leetcode 220 - remove duplicate III - using SortedSet GetViewBetween API
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace Leetcode220_ContainDuplicateIII | |
{ | |
/// <summary> | |
/// Leetcode 220 - contains duplicate III | |
/// https://leetcode.com/problems/contains-duplicate-iii/#/description | |
/// </summary> | |
class Leetcode220_ContainDuplicateIII | |
{ | |
static void Main(string[] args) | |
{ | |
} | |
/// <summary> | |
/// code review on June 29, 2017 | |
/// understand C# SortedSet GetViewBetween API | |
/// </summary> | |
/// <param name="nums"></param> | |
/// <param name="k"></param> | |
/// <param name="t"></param> | |
/// <returns></returns> | |
public bool ContainsNearbyAlmostDuplicate(int[] nums, int k, int t) | |
{ | |
if (t < 0) | |
{ | |
return false; | |
} | |
var binarySearchTree = new SortedSet<long>(); | |
for (int i = 0; i < nums.Length; i++) | |
{ | |
var visit = (long)nums[i]; | |
if (binarySearchTree.GetViewBetween(visit - t, visit + t).Count > 0) | |
{ | |
return true; | |
} | |
binarySearchTree.Add(nums[i]); | |
// remove node | |
if (i >= k) | |
{ | |
// move the node out of tree by the range - k, one node a time | |
var nodeKStepAway = nums[i - k]; | |
binarySearchTree.Remove(nodeKStepAway); | |
} | |
} | |
return false; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment