求两个集合/数组的交集

A = [9, 1, 4, 2, 5] k个整数
B = [3, 1, 8, 7, 6, 5] n个整数
Intersection => [1, 5]

复杂度理论证明

问题复杂度下限

设A为较小的列表,B为较大的列表,则k<n。

对于A中的每个元素都要查看B中是否有相同元素。查看B中是否有相同元素的时间复杂度至少为O(1),A需要迭代每个元素,所以问题复杂度时间下限为O(k)。

根据复杂度关系,空间复杂度小于等于时间复杂度[ref]””. . . [].

继续阅读

检查链表是否有环,带数学推导

推导

给定下列列表(4指回2),若有快慢两个指针,慢指针每次前进一步,快指针每次前进两步,求两指针何处相遇?

1-2-3-4
  |___|

解:

设两指针前进n次。n必定大于等于1。

In[]:=Reduce[Mod[n – 1, 3] == Mod[2n – 1, 3], n, Integers]Out[]:=\(c_1\in \mathbb{Z}\land n=3 c_1\)

然后寻找满足上述条件(Out[1])的最小的n。

In[]:=

继续阅读

MediaWiki建博客尝试

承接《博客标记语言的思考》,因为latex、维基代码都可以写博客,而且Mediawiki的模板功能实在很好用,所以先前有稍微评估了一下MediaWiki建博客网站的可能性。博客的一个重要功能是能让访客评论,我发现MediaWiki有Comments扩展程序能实现这个功能,于是趁圣诞节假期部署了Mediawiki。本文总结一下这次尝试。

我的运行环境是Windows+IIS+MySQL。用Web平台安装程序安装MediaWiki挺顺利的。MediaWiki社区建议把MediaWiki安装在/w。然后我想要设置url重写,生成短链接。这里我参照了Manual:Short URL/IIS7,就[……]

继续阅读

Mathematica笔记:函数类型

Mathematica的函数,按是否对参数求值为分二类:1、必求值,2、可能求值。

数学函数(如Sum、Integrate)在参数含有符号时不求值。

结构函数(如Level、Position)总会求值。

查询函数(如AtomQ、IntegerQ)总会求值。这类函数的函数名总是以Q结尾,且总是返回true或false。

 

Majority Element用线性时间常数空间查找超过一定频率的元素

题目来自https://oj.leetcode.com/problems/majority-element/

分析部分摘抄自《线性时间查找固定频率的元素》,有改写。

题目

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exi[……]

继续阅读

零基础求矩阵特征值和特征向量



虽然说零基础,但你还是不得不掌握行列式的求法。本文的矩阵都是低阶的,不讲述一般性的、N阶矩阵的解法。

特征值和(右)特征向量的定义

假设 A 是一个方阵。若一个非\(\vec{0}\)的向量\(\vec{x}\)满足下面的等式

\(A\vec{x}=\lambda\vec{x}\)

则\(\vec{x}\)为矩阵A的(右)特征向量,而\(\lambda\)是矩阵 A 相对于\(\vec{x}\)的特征值。[5]一个[……]

继续阅读