Code – 第77页

[swift] LeetCode 347. Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.
For example,
Given [1,1,1,2,2,3] and k = 2, return [1,2].
Note:
You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {
    var dict = [Int:Int]()
    nums.forEach {
        dict[$0] = (dict[$0] == nil ? 0 : dict[$0]! ) + 1
    }

    return dict.sorted(by:  { $0.value > $1.value } )[0..<k].map({$0.key})
}

func topKFrequent(_ nums: [Int], _ k: Int) -> [Int] {

var dict = [Int:Int]()

nums.forEach {

dict[$0] = (dict[$0] == nil ? 0 : dict[$0]! ) + 1

}

return dict.sorted(by: { $0.value > $1.value } )[0..<k].map({$0.key})

}

[swift] LeetCode 338. Counting Bits

Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1’s in their binary representation and return them as an array.

Example:
For num = 5 you should return [0,1,1,2,1,2].

Follow up:

It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
Space complexity should be O(n).
Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.

func countBits(_ num: Int) -> [Int] {
    var arr = Array(repeating: 0, count: num+1), i = 0
    while i <= num {
        arr[i] = i.nonzeroBitCount
        i += 1
    }

    return arr
}

func countBits(_ num: Int) -> [Int] {

var arr = Array(repeating: 0, count: num+1), i = 0

while i <= num {

arr[i] = i.nonzeroBitCount

i += 1

}

return arr

}

[swift] 287. Find the Duplicate Number

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

1	Input: [1,3,4,2,2] Output: 2

Example 2:

Input: [3,1,3,4,2]
Output: 3

1 2	Input: [3,1,3,4,2] Output: 3

Note:

You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n²).
There is only one duplicate number in the array, but it could be repeated more than once.

func findDuplicate(_ nums: [Int]) -> Int {
    let sn = nums.sorted()
    var i = 1
    while i < nums.count {
        if sn[i-1] == sn[i] { return sn[i] }
        i += 1
    }

    return -1
}

func findDuplicate(_ nums: [Int]) -> Int {

let sn = nums.sorted()

var i = 1

while i < nums.count {

if sn[i-1] == sn[i] { return sn[i] }

i += 1

}

return -1

}

[swift] LeetCode 283. Move Zeroes

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

var j = 0
for i in 0..<nums.count {
    if nums[i] != 0 {
        nums[j] = nums[i]
        j += 1
    }
}
for i in j..<nums.count {
    nums[i] = 0
}

var j = 0

for i in 0..<nums.count {

if nums[i] != 0 {

nums[j] = nums[i]

j += 1

}

for i in j..<nums.count {

nums[i] = 0

}

[swift] LeetCode 238. Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

func productExceptSelf(_ nums: [Int]) -> [Int] {
    var res = Array(repeating: 1, count: nums.count)
    var i = 0, v = 1

    while i < nums.count-1 {
        res[i+1] = res[i] * nums[i]
        i += 1
    }

    i = nums.count-2
    while i >= 0 {
        v *= nums[i+1]
        res[i] *= v
        i -= 1
    }
    return res
}

func productExceptSelf(_ nums: [Int]) -> [Int] {

var res = Array(repeating: 1, count: nums.count)

var i = 0, v = 1

while i < nums.count-1 {

res[i+1] = res[i] * nums[i]

i += 1

}

i = nums.count-2

while i >= 0 {

v *= nums[i+1]

res[i] *= v

i -= 1

}

return res

}

[swift] LeetCode 234. Palindrome Linked List

Given a singly linked list, determine if it is a palindrome.

Follow up:
Could you do it in O(n) time and O(1) space?

func isPalindrome(_ head: ListNode?) -> Bool {
    var arr = Array(repeating: -1, count: 999999), p = head
    var i = 0, j = 0

    while let q = p {
        arr[i] = q.val
        p = q.next; i+=1
    }

    j = i-1; i = 0

    while i < j {
        if arr[i] != arr[j] { return false }
        i+=1; j -= 1
    }

    return true
}

func isPalindrome(_ head: ListNode?) -> Bool {

var arr = Array(repeating: -1, count: 999999), p = head

var i = 0, j = 0

while let q = p {

arr[i] = q.val

p = q.next; i+=1

}

j = i-1; i = 0

while i < j {

if arr[i] != arr[j] { return false }

i+=1; j -= 1

}

return true

}