Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
transcript of array pair talk - April 29, 2017
using System;
class Solution
{
// linear scan -> O(n)
// space contain O(n)
// if the number is used twice - array ->
static int[,] FindPairsInTheArrayWithGivenDifference(int[] arr, int k)
{
// your code goes here a, b => "a"+"b", tuple<int,int>
IList<int[]> pairsFound = new List<int[]>();
if(arr == null || arr.Length == 0) pairsFound;
var cache = new HashSet<int>();
int length = arr.Length;
for(int i = 0; i < length ; i++)
{
var current = arr[i];
var search1 = current + k; // add to cache
var search2 = current - k;
// 1 , 3, 4 k = 1
// visit 1 , cache is empty , 1 + 1 = 2, 1-1 = 0, put cache{0,2}
// visit 3, 3 is not in cache, 3+1, 3-1=>4, 2 , put cache{0,2,4}
// visit 4, 4 is in the cache, now you need to add one or two pairs into output
// but peer maybe 3 or3, you do not save the information -> catch up design to fix the issue
// hashset -> Dictionary -> key is still number look for, but value is a list to your original value
// 3 -> key = 4, value 3,
//
// 100, visit 100, k = 2, then 102, 98 in the cache
// 102, or
if(cache.Contains(search1) || cache.Contains(search2) )
{
// have found one or two pairs number,
if(cache.Contains(search1))
pairsFound.Add(new int[]{current, search1}); // bug, do not +k or -k
if(cache.Contains(search2))
pairsFound.Add(new int[]{current, search1});
}
else
{
cache.Add(current);
//cache.Add(search2);
}
return pairsFound;
}
}
static void Main(string[] args)
{
}
}
// distinct integer
// 1 2 3 4 5 ->
// k - nonngetaive 1,
// pair with give difference 1, how many pair -> n* (n-1),
// choose two nodes from each, n, select n-1 -> 0(n*n)
// test case ascending order, for each number 1, check its right,
// gap of array 1000000, k = 2, binary search -> expedite O(logn)
// time complexity O(nlogn) find pair -> based on sort O(nlogn)
// distince, x- y = k,
// 1, k = 1, only number is 2,
// 1000, k = 5, two choice 998, or 1002
// build a hashtable extra space -> meet 1000, save hashset add 998 and 10002 in hashset,
// go over find 998, I find a pair -> O(n) -> extra space performance -> O(n)
// My solution, no binary search, one linear scan of the array, first you check if your pair is in hashset, if it is, then add 1 pair,
// if it is not, add a[i] +- k > 0, add at most 2 elements in the hashset
// continue -> negative
// k = 1, nonnegative, -1, its pair value should 0 or -2,
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment