By

文章目录
  1. 1. 题目一
  2. 2. 题目二

在找工作之际，我参加过几场笔试，大部分笔试题都是与算法相关的，仅有小部分涉及机器学习模型和方法。此外，为了好好准备笔试，我还专门找了历年的笔试题练手。在我看过的题目中，有些题目设计的相当巧妙，解决思路也是别出心裁。在此，我将这些题目记录下来，用来启发自己略显僵化的思维。

题目一

题：有一个长度为n数组A，为A[1], A[2], …, A[n]，希望得到长度为n的数组B，使B[i] = A[1]*…*A[i-1]*A[i+1]*…*A[n]，且A[1]*A[2]*…*A[n] < 2170786342381458。要求设计的算法满足：

  • 算法不能使用除法；
  • 时间复杂度为O(n)；
  • 空间复杂度为O(1)。

解：由于不能用除法，所以数组B只能通过乘法求解。根据题目要求，可以看出B中元素的特点

1
2
3
4
B[1] =   1  * A[2] * A[3] *...* A[n]  
B[2] = A[1] *   1  * A[3] *...* A[n]
...
B[n] = A[1] * A[2] *...* A[n-1] * 1

可以看出，B[1]…B[n]表达式在1之前的部分存在迭代关系，且B[n]…B[1]在1之后的部分也存在迭代关系。那么，可以通过两趟迭代求解数组B。
第一趟迭代

1
2
// 初值：B[1] = 1
B[i] = B[i-1] * A[i-1]

第二趟迭代

1
2
3
// 初值：val = A[n]
B[i-1] = B[i-1] * val
val = val * A[i-1]

根据上述迭代过程，乘法次数为(n-1) + 2(n-1) = 3n-3，使用一个变量val，因此时间复杂度是O(n)，空间复杂度是O(1)。
Java代码如下

1
2
3
4
5
6
7
8
9
10
11
12
double[] getB(double[] A, double[] B) {
    B[0] = 1.0;
    for (int i=1; i < A.length; i++) {
    	B[i] = B[i-1] * A[i-1];
    }
    double val = A[A.length - 1];
    for (int i=A.length-2; i > 0; i--) {
    	B[i] = B[i] * val;
        val = val * A[i];
    }
    return B;
}

题目二

题：有一个长度为n的数组A，数组元素是1到n的整数，其中有的整数出现多次，有的整数没有出现，设计算法找出A中每个整数出现的次数，要求时间复杂度为O(n)，空间复杂度为O(1)。
解：算法要求输出A中每个整数出现次数，需要O(n)的空间。但是题目要求的空间复杂度为O(1)，那么算法的输出必须借用数组A才可能实现，即算法的目的是将数组A转化为统计A中整数出现次数的新数组。
如何用长度为n的数组记录1到n个整数出现次数？最简单的方法是A[i]记录整数i出现次数。由于A中元素是1到n的整数，为了避免整数元素与出现次数混淆，我们对出现次数取负，遍历结束后，再取次数的绝对值作为输出结果。
算法流程：

  1. i = 1;
  2. 若A[i] <= 0, 转到3; 否则, 记j = A[i], A[i] = 0. 若A[j] <= 0, A[j] -= 1, 转到3; 否则, A[i] = A[j], A[j] = -1, 继续执行2;
  3. i++. 若i <= n, 转到2; 否则，转到4;
  4. i = 1,2,…,n, A[i] = -A[i].

算法思路是：先判断A[i]是否是原始数值。若A[i]是数值i的出现次数（零或负整数），那么转到下一个元素A[i+1]；若A[i]是原始数值（正整数），记j = A[i]，将A[i]赋为零，判断A[j]是否是数值j的出现次数。若A[j]是数值j的出现次数（零或负整数），那么更新A[j]，再转到下一个元素A[i+1]；若A[j]是原始数值（正整数），那么将A[j]的值赋给A[i]，将j出现的次数A[j]赋为-1，再转到A[i]进行判断。
算法在最坏的情况下，比较的次数是2n + (n-1) = 3n-1，使用一个变量j，因此时间复杂度是O(n)，空间复杂度是O(1)。
Java代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void count(int[] A) {
    // Java数组下标从0开始，采用A[i]记录整数i+1的出现次数
    for (int i=0; i < A.length; i++) {
        if (A[i] > 0) {
            int j = A[i];
            A[i] = 0;
            if (A[j-1] <= 0) {
                A[j-1] -= 1;
            } else {
                A[i] = A[j-1];
                A[j-1] = -1;
                i--;
            }
        }
    }
    for (int i=0; i < A.length; i++) {
    	A[i] = -A[i];
    }
    return;
}
文章目录
  1. 1. 题目一
  2. 2. 题目二