数组数列问题¶

这部分的问题都集中在数据集合上。主要有：

数组排序
top-k
子数组
多个数组合并，交集

解决这一类问题时，可以从以下几个方面考虑：

万能的蛮力穷举
散列表空间换事件
分治法，然后归并（归并排序）
选择合适的数据结构可以显著提高算法效率（堆排序求 top-k）
对无序的数组先排序，使用二分
贪心算法或动态规划

Fibonacci 数列¶

题目：定义 Fibonacci 数列如下：

  0 n=0
  f(n)= 1 n=1
   f(n-1)+f(n-2) n=2

输入 n，用最快的方法求该数列的第 n 项。

思路一：递归，虽然 fibonacci 数列是 递归 的经典应用，但递归效率很差，会有很多重复的计算，复杂度是成指数递增的,我测试了下计算 50 的时候已经要 300s 了。

int fib(int N) {
    if (N == 1 || N == 2) return 1;
    return fib(N - 1) + fib(N - 2);
}

思路二：从下往上计算，复杂度 O（N），一个循环就搞定

public int fib(int n){
        if (n == 0) return 0;

        //缓存
        int[] dp = new int[n + 1];

        // base case
        dp[0] = 0; dp[1] = 1;

        // 状态转移
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }

说一个细节优化点，当前状态只和之前的两个状态有关，其实并不需要那么长的一个 DP table 来存储所有的状态，只要想办法存储之前的两个状态就行了。所以，可以进一步优化，把空间复杂度降为 O(1)：

int fib(int n) {
    if (n < 1) return 0;
    if (n == 2 || n == 1) 
        return 1;
    int prev = 1, curr = 1;
    for (int i = 3; i <= n; i++) {
        int sum = prev + curr;
        prev = curr;
        curr = sum;
    }
    return curr;
}

递减数列左移后的数组中找数¶

一个数组是由一个递减数列左移若干位形成的，比如 {4，3，2，1，6，5} 是由 {6，5，4，3，2，1} 左移两位形成的，在这种数组中查找某一个数。

右移，二分查找。找到最小的数，右移到第一个位置的时候，右移完成 O(N)
直接二分查找

给出一个洗牌算法¶

给出洗牌的一个算法，并将洗好的牌存储在一个整形数组里

分析：扑克牌 54 张 2~10,J,Q,K,A,小王，大王

1）产生随机数，随机数 rand()%54 ,rand() 每次运行都一样，要改为 srand(time(NULL)) 2) 遍历数组, 随机数 k 属于区间 [i,n]，然后 a[i] 和随机数 a[k] 对换

重合区间最长的两个区间段¶

在一维坐标轴上有 n 个区间段，求重合区间最长的两个区间段如【-7，21】，【4，23】，【14，100】，【54，76】

思路一：两两比较，复杂度 N^2 思路二：先排序 + 分而治之

在一个 int 数组里查找这样的数，它大于等于左侧所有数，小于等于右侧所有数。直观想法是用两个数组 a、b。a[i]、b[i] 分别保存从前到 i 的最大的数和从后到 i 的最小的数，一个解答：这需要两次遍历，然后再遍历一次原数组，将所有 data[i]>=a[i-1]&&data[i]<=b[i] 的 data[i] 找出即可。给出这个解答后，面试官有要求只能用一个辅助数组，且要求少遍历一次。

一排 N（最大１Ｍ）个正整数 +1 递增，乱序排列，第一个不是最小的，把它换成 -1，最小数为ａ且未知。求第一个被 -1 替换掉的数原来的值，并分析算法复杂度。

[4,3,5,2,7,6] 题目啥意思？

正整数序列 Q 中的每个元素都至少能被正整数 a 和 b 中的一个整除，现给定 a 和 b，需要计算出 Q 中的前几项，例如，当 a=3，b=5，N=6 时，序列为 3，5，6，9，10，12 (1)、设计一个函数 void generate（int a,int b,int N ,int * Q）计算 Q 的前几项 (2)、设计测试数据来验证函数程序在各种输入下的正确性。

分析：这个输出序列是要递增排列思路一：类似对 2 各数组 merge，取 min( A[i],B[j]) .复杂度 O(N) 不过这里要注意，去掉 a， b 的公倍数。如 3，5 都有 15 可以整除

把数组排成最小的数¶

题目：输入一个正整数数组，将它们连接起来排成一个数，输出能排出的所有数字中最小的一个。例如输入数组 {32, 321}，则输出这两个能排成的最小数字 32132。请给出解决问题的算法，并证明该算法。

旋转数组中的最小元素。¶

题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个排好序的数组的一个旋转，输出旋转数组的最小元素。例如数组 {3, 4, 5, 1, 2} 为 {1, 2, 3, 4, 5} 的一个旋转，该数组的最小值为 1。

分析：这道题最直观的解法并不难。从头到尾遍历数组一次，就能找出最小的元素，时间复杂度显然是 O(N)。但这个思路没有利用输入数组的特性，我们应该能找到更好的解法。

约瑟夫环问题¶

n 个数字（0,1,…,n-1）形成一个圆圈，从数字 0 开始，每次从这个圆圈中删除第 m 个数字（第一个为当前数字本身，第二个为当前数字的下一个数字）。当一个数字删除后，从被删除数字的下一个继续删除第 m 个数字。求出在这个圆圈中剩下的最后一个数字。

如 0,1,2,3,4,5 删除第 2 个数字（n=6，m=2）第一次删除：1 第二次删除: 3 第三次删除：5 第四次删除：2 因此，左后的一个数字就是 4

从数学上分析下规律：

求最大重叠区间大小¶

题目描述：请编写程序，找出下面“输入数据及格式”中所描述的输入数据文件中最大重叠区间的大小。对一个正整数 n ，如果 n 在数据文件中某行的两个正整数（假设为 A 和 B）之间，即 A<=n<=B 或 A>=n>=B ，则 n 属于该行；如果 n 同时属于行 i 和 j ，则 i 和 j 有重叠区间；重叠区间的大小是同时属于行 i 和 j 的整数个数。

例如，行（10 20）和（12 25）的重叠区间为 [12 20] ，其大小为 9，行 (20 10) 和（ 20 30 ）的重叠区间大小为 1 。

四对括号可以有多少种匹配排列方式¶

比如两对括号可以有两种：（）（）和（（））

两两之差绝对值最小的值¶

有一个整数数组,请求出两两之差绝对值最小的值,记住，只要得出最小值即可，不需要求出是哪两个数。如 [-1， 3， 5， 9] 绝对值最小的是 2（5-3）

最短区间问题如果是有重复元素，那最小值就是 0 了

解题思路: 可以将这个问题转化为 ”求最大字段和“ 问题。。。

数值是否连续相邻¶

一个整数数列，元素取值可能是 0~65535 中的任意一个数，相同数值不会重复出现。0 是例外，可以反复出现。请设计一个算法，当你从该数列中随意选取 5 个数值，判断这 5 个数值是否连续相邻。注意： - 5 个数值允许是乱序的。比如： 8 7 5 0 6 - 0 可以通配任意数值。比如：8 7 5 0 6 中的 0 可以通配成 9 或者 4 - 0 可以多次出现。 - 复杂度如果是 O(n2) 则不得分。

这个问题跟”扑克牌顺子“判断问题一样，通过比较 0 的个数和相邻数字之间间隔总和来判断所有数是否连续。

////////////// 数列 ///////////////

给出两个集合 A 和 B，其中集合 A={name}，集合 B={age、sex、scholarship、address、...}，

要求：问题 1、根据集合 A 中的 name 查询出集合 B 中对应的属性信息；问题 2、根据集合 B 中的属性信息（单个属性，如 age<20 等），查询出集合 A 中对应的 name。