类别归档:算法

In mathematics and computer science, an algorithm is a self-contained step-by-step set of operations to be performed. Algorithms exist that perform calculation, data processing, and automated reasoning.

RSS feed of 算法

Python实现整数均分

将整数m划分为n个整数,使得到的整数之间的差值不超过1,结果按照升序排列。

例如输入55, 6,返回[9, 9, 9, 9, 9, 10]。

Python代码:

def splitInteger(m, n):
    assert n > 0
    quotient = m / n
    remainder = m % n
    if remainder > 0:
        return [quotient] * (n - remainder) + [quotient + 1] * remainder
    if remainder ...

继续阅读

[LeetCode题解]从两个有序数组的并集中寻找第k小元素

Given two sorted arrays A, B of size m and n respectively. Find the k-th smallest element in the union of A and B. You can assume that there are no duplicate elements.

不得不承认这道题目解决起来非常的巧妙。像大多数难题一样,需要经过非常巧妙的观察才可以用简洁的方式求解。

朴素解法, O(m+n ...

继续阅读

寻找数组第k大元素的线性时间选择算法

给定一个包含n个元素的数组,怎样从中找出第k大的数。

What is the most efficient algorithm to find the kth smallest element in an array having n elements?

此问题被称为求第k顺序统计量(kth order statistic)。

求解该问题的线性时间算法(既包括确定性算法,也包括非确定性算法)列举如下:

1. Quickselect (快速选择)

2. Median-of-medians (BFPRT) (中位数的中位数)

3. Introselect (内省选择)

4. Unnamed ...

继续阅读