Quick Sort:
Reference: www.zhihu.com/question/48…
This blog clearly explains the principle of quick sort algorithm.
fun quickSortInner(array: IntArray, left: Int, right: Int) {
// The termination condition of recursive
if (left < right) {
val index: Int = findIndex(array, left, right)
quickSortInner(array, left, index - 1)
quickSortInner(array, index + 1, right)
}
}
fun findIndex(array: IntArray, left: Int, right: Int): Int {
var l = left
var r = right
val sentry = array[left]
while (l < r) {
while (l < r && array[r] > sentry) {
r--
}
// Do not change l index here, though the num in l position is already smaller than sentry.
// Otherwise, the l will move to the next position of the final one.
array[l] = array[r]
while (l < r && array[l] <= sentry) {
l++
}
array[r] = array[l]
}
array[l] = sentry
return l
}
Leetcode 169.Majority Element
Description:
Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.
Example 1:
Input: nums = [3,2,3]
Output: 3
Solution:
If there is a majority element in an array, it will always remain in the lead, even after encountering other elements.
fun majorityElement(nums: IntArray): Int {
var candidate = nums[0]
var count = 1
for (i in 1 until nums.size) {
if (candidate != nums[i]) {
if (count == 0) {
candidate = nums[i]
} else {
count--
}
} else {
count++
}
}
return candidate
}
Why i was wrong.? When I first saw this question, what I thought is that could i use the findindex method in quick sort. So the majority will occupy more than half of the array, and the half one is the answer. Unfortunately, I was wrong. If the sentry is the element which apprears more than 1/2, then the position of the 1/2 array may not be this element. For example, [4,5,4] after first quick sort traverse, it also the [4,5,4]. This function only makes sure the element large or equal than sentry will move to the end fo the queue, but does not guarantee the sentry will move to the 1/2 position.
Binary Search
Leetcode 35.Search insert position
Description:
Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.
Input: nums = [1,3,5,6], target = 5
Output: 2
Solution:
fun searchInsert(nums: IntArray, target: Int): Int {
var l = 0
var r = nums.size - 1
while (l <= r) {
val mid = l + (r - l) / 2
if (nums[mid] == target) {
return mid
} else if (nums[mid] > target) {
r = mid - 1
} else {
l = mid + 1
}
}
// target does not be found in the array, l will stop at the position that target should be insert.
// nums[l] is the smallest number in greater than target.
return l
}
Leetcode 450.Delete Node in a BST
Description:
Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.
Basically, the deletion can be divided into two stages:
- Search for a node to remove.
- If the node is found, delete the node.
Example 1:
Input: root = [5,3,6,2,4,null,7], key = 3
Output: [5,4,6,2,null,null,7]
Explanation: Given key to delete is 3. So we find the node with value 3 and delete it.
One valid answer is [5,4,6,2,null,null,7], shown in the above BST.
Please notice that another valid answer is [5,2,6,null,4,null,7] and it's also accepted.
Solution:
we need to handle different cases:
- if the node is a leaf(no children), simply remove it by returning null.
- if the node has one child, connect the child directly to its parent by returning the child node.
- if the node has two children, find the in-order successor, copy its value to the current node, and recursively delete the in-order successor.
Recursive method:
class Solution {
public static TreeNode inorderSuccessor(TreeNode root) {
while(root.left != null) {
root = root.left;
}
return root;
}
public TreeNode deleteNode(TreeNode root, int key) {
if(root == null) return root;
if(root.val > key) {
root.left = deleteNode(root.left, key);
}
else if(root.val < key) {
root.right = deleteNode(root.right, key);
}
else { // key == root.data;
//case 1 ---> while both node null
if(root.left == null && root.right == null) {
return null;
}
//case - 2 -----> while a single node is null
else if(root.left == null) {
return root.right;
}
else if(root.right == null) {
return root.left;
}
//case - 3 -----> while it has both nodes
else {
// find the new middle value
TreeNode ios = inorderSuccessor(root.right);
root.val = ios.val;
root.right = deleteNode(root.right, ios.val);
}
}
return root;
}
}
Non-recursive method
fun deleteNode(root: TreeNode?, key: Int): TreeNode? {
// key's parent
var prev: TreeNode? = null
var node = root
// find the key
while (node != null && node.`val` != key) {
prev = node
node = if (key < node.`val`) {
node.left
} else {
node.right
}
}
// key is not in the tree
if (node == null) {
return root
}
// key is in the tree
// merge the child nodes, let the subtree add to the parent
var mergedRoot: TreeNode? = null
// case 1: no child
if (node.left == null && node.right == null) {
mergedRoot = null
}
// case 2: only one child
if (node.left == null || node.right == null) {
mergedRoot = if (node.left != null) node.left else node.right
}
// case 3: two children
if (node.left != null && node.right != null) {
val value = node.left!!.`val`
var temp = node.right
while (temp != null) {
if (value <= temp.`val`) {
if (temp.left == null) {
temp.left = node.left
break
}
temp = temp.left
} else {
if (temp.right == null) {
temp.right = node.left
break
}
temp = temp.right
}
}
mergedRoot = node.right
}
// key is the root
if (prev == null) {
return mergedRoot
}
// key is not root
if (prev.`val` > key) {
prev.left = mergedRoot
} else {
prev.right = mergedRoot
}
return root
}
