题目: 在排序数组中,找出给定数字出现的次数 思路: 既然出现排序数组,很容易想到二分查找,时间复杂度为O(logn); 先通过二分查找找到最左边出现该数字的下标left(如果没找到,则返回-1),然后通过二分查找找到最…
分类:数组相关算法
(算法)AA制
题目: A、B、C、D四个人去吃大餐,吃饭去说好,付钱时AA制,但最后结账时,因为4个人带的钱不一样多,最后A付了112元,B付了86元,C付了10元,D没带钱,所以没有付; 但AA制需要平摊餐费,所以需要设计一种方案来…
(算法)只出现两次的最小数
题目: 给定一数组,里面的数字为1~N,每个数出现一次或两次,求只出现一次的最小数。 要求: 空间复杂度:O(1),时间复杂度:O(n) 思路: 题目给定的数字为1~N,因此可以通过交换的方法,将数组下标与数字对应存放,…
(算法)和为0的最大连续子数组
题目: 和为零的最大连续子数组 思路: 我首先想到的是前缀数组和,遍历一遍数组,计算出sum[i](表示从0-i的子数组之和)。 有了前缀数组和,只要sum[i]=sum[j](i<j),那么区间[i+1,j]就是…
(算法)旋转有序数组中查找某个数
题目: 假设有个有序数组在某个位置旋转,得到新的数组,即为旋转有序数组。如:(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). 现给定一个这样…
(笔试题)把一个整数数组中重复的数字去掉
题目: 把一个整数数组中重复的数字去掉,并输出剩下的不重复的元素。(要求不能开辟新空间) 思路: 先排序,然后遍历数组比较,详见代码 代码: #include <iostream> #include <…
(笔试题)区间最大重叠
题目: 在一维坐标轴上有n个区间段,求重合区间最长的两个区间段。 区间段的数据结构定义如下: struct Interval{ int start; int end; }; 思路: 首先按照区间的左端点即start对n个…
(算法)求矩阵转置
题目: 编写一个函数,输入为一个矩阵,打印这个矩阵转置后的结果。 例: 输入矩阵是 1,2,3,4 5,6,7,8 9,10,11,12 13,14,15,16 打印结果应该是 13,9,5,1 14,10…
(算法)两个有序数组的第k大的数
题目: 有两个数组A和B,假设A和B已经有序(从大到小),求A和B数组中所有数的第K大。 思路: 1、如果k为2的次幂,且A,B 的大小都大于k,那么 考虑A的前k/2个数和B的前k/2个数, 如果A[k/2]<B…
(算法)字典序数列
题目: 给定正整数N,要求对1~N的所有数按照字典序来排列, 如: 1-10:1 10 2 3 4 5 6 7 8 9 1-100:1 10 100 11 12 13 14 15 16 17 18 19 2 20 21 …