我要投稿 投诉建议

常见的算法面试题解法

时间:2021-04-10 09:47:39 面试试题 我要投稿

常见的算法面试题解法

  大部分常用的排序算法时间复杂度都是O(nLogn)

常见的算法面试题解法

  这个只能说是通用解,一般解

  对于算法面试题中往往要求很低的时间复杂度,

  例如下面这个题目

  已知一个数组长为m 中间存放的都是整数 其值范围为1-m ,中间的元素有可能重复 也有可能不重复

  如何在O(M)的情况下查到 (1-m)的数中 哪些数重复了,哪些数没有出现

  counting sort 的本质是 新建一个长度为M的`数组An 每一个数组下标代表一个数 ,数组中的值代表这个元素出现的次数 (初始值都为0)

  那么, 遍历一次m 遇到一个数 就在对应的下标上加1

  那么最终可以得到一个An 其中包含了所有元素的出现个数

  将其展开 就可以获得排序完的数组

  这是一种特殊的算法,只能解决特殊的问题 但是他的时间复杂度是O(n)

  如果在你遇到排序 或者查找之类的算法题的时候,不如上去先试试counting sort

【常见的算法面试题解法】相关文章:

最常见的面试题09-17

4个常见的面试题08-08

常见的软件测试面试题06-06

常见软件测试面试题05-10

酒店销售常见面试题08-11

常见面试题回答点评08-04

常见.net面试题及答案06-19

常见的企业面试题目有哪些08-11

常见的英语面试题目及技巧08-08