SHARE
TWEET

Untitled

a guest Apr 23rd, 2019 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //Successor with delete. Given a set of nn integers S={0,1,...,n−1} and a sequence of requests of the following form:
  2. //
  3. //Remove x from S
  4. //Find the successor of x: the smallest y in S such that y≥x.
  5. //design a data type so that all operations (except construction) take logarithmic time or better in the worst case.
  6.  
  7. import Foundation
  8.  
  9.  
  10. class Seq {
  11.     var dict = [Int: Int]()
  12.     init(_ set: Set<Int>) {
  13.         dict[-1] = -1
  14.         for item in set {
  15.             dict[item] = item
  16.         }
  17.     }
  18.    
  19.     private func root(x: Int) -> Int {
  20.         var i = x
  21.         while i != dict[i] {
  22.             dict[i] = dict[dict[i]!]
  23.             i = dict[i]!
  24.         }
  25.         return i
  26.     }
  27.    
  28.     func remove(_ x: Int) {
  29.         guard x >= 0 else {
  30.             return
  31.         }
  32.         dict[x] = root(x: x - 1)
  33.     }
  34.    
  35.     func find(_ x: Int) -> Int? {
  36.         let r = root(x: x)
  37.         return r >= 0 ? r : nil
  38.     }
  39. }
  40.  
  41. let seq = Seq(Set<Int>([0,1,2,3,4,5,6]))
  42. seq.remove(1)
  43. seq.remove(2)
  44. seq.remove(3)
  45. seq.find(3)
  46. //[0:0, 1:1, 2:2, 3:3, 4:4, 5:5]
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top