最新字节跳动面试题与答案: 无序数组的中位数 (快排思想O(N) 时间复杂度)

1.算法题一：无序数组的中位数 (快排思想O(N) 时间复杂度)

import org.junit.jupiter.api.Testimport java.util.*

/** * 1.算法题一：无序数组的中位数 (快排思想O(N) 时间复杂度) * 中位数定义: 如果数组长度是奇数，最中间就是位置为(n+1)／2的那个元素。如果是偶数，就是位置为n/2和位置为n/2+1的两个元素的和除以2的结果. * 例如，[2,3,4] 的中位数是 3[2,3] 的中位数是 (2 + 3) / 2 = 2.5 */class ArrayMidNum {

@Test fun main() { val m1 = median(intArrayOf(2, 3, 4)) val m2 = median(intArrayOf(2, 3)) println("m1=$m1") println("m2=$m2") //m1=3.0 //m2=2.5 }

fun median(array: IntArray): Double { val N = array.size val heapSize = N / 2 + 1

// PriorityQueue通过二叉小顶堆实现，可以用一棵完全二叉树表示(任意一个非叶子节点的权值，都不大于其左右子节点的权值)， // 也就意味着可以通过数组来作为PriorityQueue的底层实现。

// 首先将数组的前(n+1)／2个元素建立一个最小堆。 val heap = PriorityQueue(heapSize) for (i in 0..heapSize - 1) { heap.add(array[i]) }

// 然后，对于下一个元素 array[i] ，和堆顶的元素 heap.peek() 比较，如果 array[i] heap.peek() ，则用该元素取代堆顶，再调整堆，接着看下一个元素。重复这个步骤，直到数组为空。 for (i in heapSize..N - 1) { if (array[i] > heap.peek()) { heap.poll() heap.add(array[i]) } } // 当数组都遍历完了，那么，堆顶的元素即是中位数。 // 如果数组长度是奇数，最中间就是位置为(n+1)／2的那个元素。如果是偶数，就是位置为n/2 和位置为 n/2+1 的两个元素的和除以2的结果 if (N % 2 == 1) { return (heap.peek()).toDouble() } else { // poll()方法获取并删除队首元素 val a = heap.poll() val b = heap.peek() return (a + b) / 2.0 }

// 可以看出，长度为(n＋1)／2的最小堆是解决方案的精华之处。 }

}

2.算法题二：给一数组，让你找一对满足：i