First Unique Number: priority queue, hash tables and math
Tough problem: https://leetcode.com/problems/first-unique-number/
Here is the approach:
A) Have a priority queue instead of a regular queue
B) The priority should be a combination of the value count and the value order. The value count is more important, the order is used as a tie-breaker. Look at the constraints of the problem and you can come up with a simple formula for the priority
C) In a hash table, store the count of each number
D) The ShowFirstUnique becomes trivial: if the head (via a Peak method) has one occurrence, return it, otherwise -1
E) When adding in the queue, make sure to check whether the element is the first, if so dequeue first
Code is down below, cheers, ACC.
public class FirstUnique
{
private PriorityQueue pQueue = new PriorityQueue("up");
private Hashtable count = new Hashtable();
private long order = 0;
private const long M = 100000001;
public FirstUnique(int[] nums)
{
foreach(int n in nums)
{
if (!count.ContainsKey(n)) count.Add(n, 0L);
count[n] = (long)count[n] + 1;
if (pQueue.Count > 0 && (int)pQueue.Peak() == n)
{
pQueue.Dequeue();
}
order++;
pQueue.Enqueue(n, (long)count[n] * M + order);
}
}
public int ShowFirstUnique()
{
if (pQueue.Count == 0) return -1;
int peak = (int)pQueue.Peak();
if ((long)count[peak] == 1) return peak;
return -1;
}
public void Add(int value)
{
if (!count.ContainsKey(value)) count.Add(value, 0L);
count[value] = (long)count[value] + 1;
if (pQueue.Count > 0 && (int)pQueue.Peak() == value)
{
pQueue.Dequeue();
}
order++;
pQueue.Enqueue(value, (long)count[value] * M + order);
}
}
public class PriorityQueue
{
public struct HeapEntry
{
private object item;
private long priority;
public HeapEntry(object item, long priority)
{
this.item = item;
this.priority = priority;
}
public object Item
{
get
{
return item;
}
}
public long Priority
{
get
{
return priority;
}
}
}
private int direction = 0; //0 - up, 1 - down
private int count;
private int capacity;
public HeapEntry[] heap;
public int Count
{
get
{
return this.count;
}
}
public PriorityQueue(string directionStr)
{
direction = directionStr.Equals("up") ? 0 : 1;
capacity = 1000000;
heap = new HeapEntry[capacity];
}
public object Peak()
{
return heap[0].Item;
}
public object Dequeue()
{
object result = heap[0].Item;
//priority = heap[0].Priority;
count--;
trickleDown(0, heap[count]);
return result;
}
public void Enqueue(object item, long priority)
{
count++;
bubbleUp(count - 1, new HeapEntry(item, priority));
}
private void bubbleUp(int index, HeapEntry he)
{
int parent = (index - 1) / 2;
// note: (index > 0) means there is a parent
if (direction == 0)
{
while (index > 0 && heap[parent].Priority > he.Priority)
{
heap[index] = heap[parent];
index = parent;
parent = (index - 1) / 2;
}
}
else
{
while (index > 0 && heap[parent].Priority < he.Priority)
{
heap[index] = heap[parent];
index = parent;
parent = (index - 1) / 2;
}
}
heap[index] = he;
}
private void trickleDown(int index, HeapEntry he)
{
int child = (index * 2) + 1;
while (child < count)
{
if (direction == 0)
{
if (child + 1 < count && heap[child].Priority > heap[child + 1].Priority)
{
child++;
}
}
else
{
if (child + 1 < count && heap[child].Priority < heap[child + 1].Priority)
{
child++;
}
}
heap[index] = heap[child];
index = child;
child = (index * 2) + 1;
}
bubbleUp(index, he);
}
}
1429. First Unique Number
Medium
You have a queue of integers, you need to retrieve the first unique integer in the queue.
Implement the
FirstUnique class:FirstUnique(int[] nums)Initializes the object with the numbers in the queue.int showFirstUnique()returns the value of the first unique integer of the queue, and returns -1 if there is no such integer.void add(int value)insert value to the queue.
Example 1:
Input: ["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"] [[[2,3,5]],[],[5],[],[2],[],[3],[]] Output: [null,2,null,2,null,3,null,-1] Explanation: FirstUnique firstUnique = new FirstUnique([2,3,5]); firstUnique.showFirstUnique(); // return 2 firstUnique.add(5); // the queue is now [2,3,5,5] firstUnique.showFirstUnique(); // return 2 firstUnique.add(2); // the queue is now [2,3,5,5,2] firstUnique.showFirstUnique(); // return 3 firstUnique.add(3); // the queue is now [2,3,5,5,2,3] firstUnique.showFirstUnique(); // return -1
Example 2:
Input: ["FirstUnique","showFirstUnique","add","add","add","add","add","showFirstUnique"] [[[7,7,7,7,7,7]],[],[7],[3],[3],[7],[17],[]] Output: [null,-1,null,null,null,null,null,17] Explanation: FirstUnique firstUnique = new FirstUnique([7,7,7,7,7,7]); firstUnique.showFirstUnique(); // return -1 firstUnique.add(7); // the queue is now [7,7,7,7,7,7,7] firstUnique.add(3); // the queue is now [7,7,7,7,7,7,7,3] firstUnique.add(3); // the queue is now [7,7,7,7,7,7,7,3,3] firstUnique.add(7); // the queue is now [7,7,7,7,7,7,7,3,3,7] firstUnique.add(17); // the queue is now [7,7,7,7,7,7,7,3,3,7,17] firstUnique.showFirstUnique(); // return 17
Example 3:
Input: ["FirstUnique","showFirstUnique","add","showFirstUnique"] [[[809]],[],[809],[]] Output: [null,809,null,-1] Explanation: FirstUnique firstUnique = new FirstUnique([809]); firstUnique.showFirstUnique(); // return 809 firstUnique.add(809); // the queue is now [809,809] firstUnique.showFirstUnique(); // return -1
Constraints:
1 <= nums.length <= 10^51 <= nums[i] <= 10^81 <= value <= 10^8- At most
50000calls will be made toshowFirstUniqueandadd.
Accepted
39
Submissions
75,747
Here is the approach:
A) Have a priority queue instead of a regular queue
B) The priority should be a combination of the value count and the value order. The value count is more important, the order is used as a tie-breaker. Look at the constraints of the problem and you can come up with a simple formula for the priority
C) In a hash table, store the count of each number
D) The ShowFirstUnique becomes trivial: if the head (via a Peak method) has one occurrence, return it, otherwise -1
E) When adding in the queue, make sure to check whether the element is the first, if so dequeue first
Code is down below, cheers, ACC.
public class FirstUnique
{
private PriorityQueue pQueue = new PriorityQueue("up");
private Hashtable count = new Hashtable();
private long order = 0;
private const long M = 100000001;
public FirstUnique(int[] nums)
{
foreach(int n in nums)
{
if (!count.ContainsKey(n)) count.Add(n, 0L);
count[n] = (long)count[n] + 1;
if (pQueue.Count > 0 && (int)pQueue.Peak() == n)
{
pQueue.Dequeue();
}
order++;
pQueue.Enqueue(n, (long)count[n] * M + order);
}
}
public int ShowFirstUnique()
{
if (pQueue.Count == 0) return -1;
int peak = (int)pQueue.Peak();
if ((long)count[peak] == 1) return peak;
return -1;
}
public void Add(int value)
{
if (!count.ContainsKey(value)) count.Add(value, 0L);
count[value] = (long)count[value] + 1;
if (pQueue.Count > 0 && (int)pQueue.Peak() == value)
{
pQueue.Dequeue();
}
order++;
pQueue.Enqueue(value, (long)count[value] * M + order);
}
}
public class PriorityQueue
{
public struct HeapEntry
{
private object item;
private long priority;
public HeapEntry(object item, long priority)
{
this.item = item;
this.priority = priority;
}
public object Item
{
get
{
return item;
}
}
public long Priority
{
get
{
return priority;
}
}
}
private int direction = 0; //0 - up, 1 - down
private int count;
private int capacity;
public HeapEntry[] heap;
public int Count
{
get
{
return this.count;
}
}
public PriorityQueue(string directionStr)
{
direction = directionStr.Equals("up") ? 0 : 1;
capacity = 1000000;
heap = new HeapEntry[capacity];
}
public object Peak()
{
return heap[0].Item;
}
public object Dequeue()
{
object result = heap[0].Item;
//priority = heap[0].Priority;
count--;
trickleDown(0, heap[count]);
return result;
}
public void Enqueue(object item, long priority)
{
count++;
bubbleUp(count - 1, new HeapEntry(item, priority));
}
private void bubbleUp(int index, HeapEntry he)
{
int parent = (index - 1) / 2;
// note: (index > 0) means there is a parent
if (direction == 0)
{
while (index > 0 && heap[parent].Priority > he.Priority)
{
heap[index] = heap[parent];
index = parent;
parent = (index - 1) / 2;
}
}
else
{
while (index > 0 && heap[parent].Priority < he.Priority)
{
heap[index] = heap[parent];
index = parent;
parent = (index - 1) / 2;
}
}
heap[index] = he;
}
private void trickleDown(int index, HeapEntry he)
{
int child = (index * 2) + 1;
while (child < count)
{
if (direction == 0)
{
if (child + 1 < count && heap[child].Priority > heap[child + 1].Priority)
{
child++;
}
}
else
{
if (child + 1 < count && heap[child].Priority < heap[child + 1].Priority)
{
child++;
}
}
heap[index] = heap[child];
index = child;
child = (index * 2) + 1;
}
bubbleUp(index, he);
}
}
Comments
Post a Comment
[γγ¬γΌγ ]