题目： 在排序数组中，找出给定数字出现的次数 思路： 既然出现排序数组，很容易想到二分查找，时间复杂度为O(logn)； 先通过二分查找找到最左边出现该数字的下标left（如果没找到，则返回-1），然后通过二分查找找到最…

题目： A、B、C、D四个人去吃大餐，吃饭去说好，付钱时AA制，但最后结账时，因为4个人带的钱不一样多，最后A付了112元，B付了86元，C付了10元，D没带钱，所以没有付； 但AA制需要平摊餐费，所以需要设计一种方案来…

题目： 给定一数组，里面的数字为1~N，每个数出现一次或两次，求只出现一次的最小数。 要求： 空间复杂度：O(1)，时间复杂度：O(n) 思路： 题目给定的数字为1~N，因此可以通过交换的方法，将数组下标与数字对应存放，…

题目： 和为零的最大连续子数组 思路： 我首先想到的是前缀数组和，遍历一遍数组，计算出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…

题目： 有两个数组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 …