华为od 算法岗一面

有点菜,前面问了一些项目相关

然后主要问了一个图的全部最短路径-->弗洛伊德算法

问了归并排序,问了堆的特性,这个我没答上来,我忘记堆是一种特殊的树了,错以为是一种新的数据结构

问有没有机器学习相关经验,说了自己用像素点识别做的脚本(估计想问有没有用特征识别的方法)

然后算法题有序序列的合并

比如1,3,5,7 2,4,6,8合并成 12345678

我没有理解清楚我以为是 1357,2468,12345678这样合并,每段数组长度还不一样,我写算法是用c的,c处理这种不定长的输入有点麻烦

我还是简化了一下理解成1357,2468,5678 这样都是定长的合并简化一下逻辑

但是可能面试官想问的是1357,2468这样两个数组的合并,这个双指针插入排序我做过不算难,时间复杂度O (m+n)

#include <stdio.h>
#include <string.h>

// 接收两个有序数组输入格式
// m,n 6 5
// m个数 1  3 4  6 25 36
// n个数 2 7 15 26 81
//插入排序

int main()
{
    int m, n;
    while (scanf("%d %d", &m, &n) != EOF)
    {
        int num_m[m + n], num_n[n];
        for (int i = 0; i < m; i++)
            scanf("%d", &num_m[i]);
        for (int i = 0; i < n; i++)
            scanf("%d", &num_n[i]);
        //插入排序 递增
        //双指针
        int insert = 0, pos = 0;

        while (pos < n)
        {
            while (num_n[pos] >= num_m[insert])
            {
                insert++;
            }
//将此时的 pos插入在num_m 数组的insert位置处;
//先向后移动空出位置,再插入  需要最后一个位置先动不然前面的数据会污染后面的
            //这个地方我看到有个更好的优化是两个数组的指针从尾部开始比较然后将较大的数
            //从m+n的尾部填入
            for (int i = m + n - 1; i - 1 >= insert; i--)
            {
                num_m[i] = num_m[i - 1];
            }
            num_m[insert] = num_n[pos];
            pos++;
        }
        for (int i = 0; i < m + n; i++)
            printf("%d ", num_m[i]);
        printf("\n");
    }

    return 0;
}

优化后

#include <stdio.h>
#include <string.h>

// 接收两个有序数组输入格式
// m,n 6 5
// m个数 1  3 4  6 25 36
// n个数 2 7 15 26 81
//插入排序

int main()
{
    int m, n;
    while (scanf("%d %d", &m, &n) != EOF)
    {
        int num_m[m + n], num_n[n];
        for (int i = 0; i < m; i++)
            scanf("%d", &num_m[i]);
        for (int i = 0; i < n; i++)
            scanf("%d", &num_n[i]);
        //插入排序 递增
        //双指针+插入位置
        int m_p = m - 1, n_p = n - 1;
        int pos = m + n - 1;
        while (pos>=0)
        {
            if (num_m[m_p] >= num_n[n_p])
            {
                num_m[pos--] = num_m[m_p--];
            }
            else
                num_m[pos--] = num_n[n_p--];
        }

        for (int i = 0; i < m + n; i++)
            printf("%d ", num_m[i]);
        printf("\n");
    }

    return 0;
}

这个是不是内容太少了
但是n个有序数组的合并我有思路,但是写起来太慢了

还被面试官说不会用动态数组,说最好掌握C++或者python这样的语言

他是不是没有看我在写的代码 ,没有提醒说题目是两个有序数组的合并,还是就是想问n个数组的合并呀

动态数组就是

int *num

num = (int *)malloc(sizeof(int)*n)

这样吗

我会用的,但是我以为举的是4个数字的例子就简化一下主要还是中间排序的逻辑么

然后我看了一下

网上n个有序序列的合并

C++方法

合并n个有序数组
创建一个大小为n*k的数组保存最后的结果
创建一个大小为n的最小堆，堆中元素为n个数组中的每个数组的第一个元素
重复下列步骤n*k次：
每次从堆中取出最小元素（堆顶元素），并将其存入输出数组中
用堆顶元素所在数组的下一元素将堆顶元素替换掉，
如果数组中元素被取光了，将堆顶元素替换为无穷大。每次替换堆顶元素后，重新调整堆
时间复杂度是n*k*logn

我的思路C
合并n个有序数组
创建一个大小为n*k的数组保存最后的结果
建立pos[n],初始化指向n个数组的第一个元素

重复下列步骤n*k次：
比较所指元素的最小值,存入输出数组
最小值对应的pos[index]++,指向对应数组的下一个元素
如果pos[index]大于k，说明对应数组已经取光,重新找到新的pos[index]小于等于k的数组

最后一步可以优化,第一次定义初始最小值在while循环外部,后面定义初始最小值在pos[index]++之后,如果小于k指向下一元素
如果大于k, 说明对应数组已经取光,令下一轮比较的初始最小值min = 无穷大
然后在比较的时候用if筛去pos已经大于k的数组

这样避免重新找到新的pos[index]小于等于k的数组的遍历
最后的时间复杂度是n*k*n
原因是因为在用堆排序的地方我用了遍历比较最小值

最后卡在数组已经取光,重新找到新的pos[index]小于等于k的数组,判定的地方没有写好,当时没有调试出来

后来面试官下线了才调试出来了

#include <stdio.h>
#include <string.h>


#define n 3
#define k 4
#define MAX 100
int main()
{
    int num[n][k] = {{1, 3, 5, 7}, {-1, 6, 7, 8}, {1, 2, 3, 4}};
    int pos[n] = {0};
    int res[20];
    int top = -1;

    int min;
    int index = 0;
    min = num[index][pos[index]];
    while (top < k * n - 1)
    {
      //  min = num[index][pos[index]];

        for (int i = 0; i < n; i++)
        {
            if (pos[i] <= k-1)
            {
                if (num[i][pos[i]] < min)
                {
                    min = num[i][pos[i]];
                    index = i;
                }
            }
        }
        res[++top] = num[index][pos[index]];
        pos[index]++;
        // if (pos[index] > k-1)
        // {
        //     for (int l = 0; l < n; l++)
        //         if (pos[l] <= k-1)
        //         {
        //             index = l;
        //             break;
        //         }
        // }
        if (pos[index] > k-1)
        min = MAX;
        else
        min = num[index][pos[index]];

    }

    for (int i = 0; i <= top; i++)
    {
        printf("%d ", res[i]);
    }

    return 0;
}

时间复杂度是k*n^2

当时面试官说还有优化空间说这个复杂度很大,那就是用堆排序替换那一段遍历比较最小值? 还能再降低复杂度吗

我确实没有项目经验,C++的一些特性堆,map,集合set,sort因为一直在用c刷题也都没用过

平时工作在写VBA,没啥实践机会,这阵子又在补一些网络知识三次握手四次挥手IP之类的我看其它面经里有,我也看了python的基本语法,确实还有没有好好用过C++和Python

有点难受,基础知识还差操作系统要补

现在再转用c++,python刷题我怕加上日常在用的VBA练习太短我会搞混,有人有这样多语言混用的经验吗...

感觉如果有机会二面还是再看看基础的数据结构与算法吧