数列 - 查找¶

数组中超过出现次数超过一半的数字¶

题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。

+-1 计数法

找数组里面重复的一个数¶

找数组里面重复的一个数，一个含 n 个元素的整数数组至少存在一个重复数，请编程实现，在 O（n）时间内找出其中任意一个重复数。

hash 算法，空间要求多（注意数组元素要是 int 类型），数的大小范围和数组长度 N 都可以是无穷大，这里使用 hash 算法，空间复杂度是 O(n),空间可能无法满足条件。
先排序，复杂度 n(logn); 然后遍历一遍就可以知道哪些数重复了。
高级解法：将问题转化为 判断单链表中存在环

类似问题：找出数组中唯一的重复元素

查找只出现一次的元素¶

给一个非空整数数组，比如 [2, 2, 3] ，其余元素均出现 2 次，找出那个只出现一次的元素。

思路：异或运算，成对儿的数字就会变成 0，落单的数字和 0 做异或还是它本身

int singleNumber(vector<int>& nums) {
    int res = 0;
    for (int n : nums) {
        res ^= n;
    }
    return res;
}

数组中找出某数字出现的次数¶

在排序数组中，找出给定数字的出现次数。比如 [1, 2, 2, 2, 3] 中 2 的出现次数是 3 次。

分析： 1. 因为是排序数组，可以使用二分查找 2. 将二分查找坚持到底，这样在最坏的情况下 ([2,2,2,2,2,2,2]) 都有 0(lgn) 复杂度

int binary_search_first(int *a,int length,int key);
int binary_search_lash(int *a,int length,int key);

大于 K 的最小正整数¶

给定一个集合 A=0,1,3,8，指定任意一个正整数 K，请用 A 中的元素组成一个大于 K 的最小正整数。

比如，A=[1,0] K=21 那么输出结构应该为 100。

查找最小的 k 个元素 (top-k)¶

题目：输入 n 个整数，输出其中最小的 k 个。例如输入 1，2，3，4，5，6，7 和 8 这 8 个数字，则最小的 4 个数字为 1，2，3 和 4。

topMinK(int *a,int length,int k);
topMaxK(int *a,int length, int k);

全部排序复杂度 NlogN ，数据了较大时，内存可能承受不住
部分排序维护一个大小为 K 的数组，由大到小排序，然后遍历所有数据，每个数据跟数组中最小元素比较，如果比最小元素大，就要插入数组了,这里还有寻找插入位置，移动数组元素的 cpu 消耗。复杂度是 N*K
堆排序。在这的 K 较大时（比如这道题目：2 亿个整数中求最大的 100 万之和），上面的算法还是有很多可以改进的地方，如采用二分查找定位插入位置，移动数组元素的计算是躲不过去了。那有没有什么数据结构即能 快速查找，还能快速移动元素 呢?最好是 O(1) 复杂度。

答案就是 二叉堆。我们可以遍历总量中的每个元素来跟二叉堆中的堆顶元素比较 (堆顶元素在 小根堆 中最小值，在 大根堆 中是最大值)，这样在 0(1) 复杂度就可以完成查找操作，揭下来需要的操作就是重新调整推结构，复杂度是 O(logk),因此整个操作复杂度是 O(n*logk)

top-k 小的时候用 *大根堆* ，top-k 大得时候用 *小根堆*

找第 k 大的数¶

比如 1，2，3，4，5，6，7,8 这 8 个数字，第 3 大的数字是 6

int topK(int * a, int length, int k)

//冒泡实现
    public int findK(int[] nums, int k){
        //base case
        if (nums== null || nums.length < k) {
            return -1;
        }

        for(int i=1; i<=k; i++){
            for(int j=0; j<nums.length-i; j++) {
                int next = j+1;
                if(nums[j]> nums[next]){
                    int tmp = nums[j];
                    nums[j] = nums[next];
                    nums[next] = tmp;
                }
            }
        }

        return nums[nums.length-k];
    }

/** 
     *  小根堆实现
     */
    public static int findMaxK(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(k, (a, b) -> (a-b) );

        for (int i = 0; i <nums.length ; i++) {
            //取出前k个元素放入 PQ 中
            if (i < k) {
                pq.add(nums[i]);
                continue;
            }

            Integer head = pq.peek();
            if (head < nums[i]) {//维护 priorityQueue 中元素只有k个
                pq.poll();
                pq.add(nums[i]);
            }
        }
        return pq.poll();
    }

最长公共子序列（动态规划的经典题目）¶

【最大/小差问题】求相邻元素的最大差值，有无序的实数列 V[N]，要求求里面大小相邻的实数的差的最大值，关键是要求线性空间和线性时间

如【9，-1，-11，2】最大差值 = 2-（-11） = 13

最小差 hash 合并最大差 hash 分解桶排序

桶排序 比快排还快，最耗空间

最长递增子序列¶

题目描述：设 L=是 n 个不同的实数的序列，L 的递增子序列是这样一个子序列 Lin=< aK1,ak2,…,akm >，其中 k1< k2<…< km 且 aK1< ak2<…< akm。求最大的 m 值。

如【5，6，7，3，2，8】最长子序列【5，6，7，8】

动态规划

在从 1 到 n 的正数中 1 出现的次数¶

题目：输入一个整数 n，求从 1 到 n 这 n 个整数的十进制表示中 1 出现的次数。

例如输入 12，从 1 到 12 这些整数中包含 1 的数字有 1，10，11 和 12，1 一共出现了 5 次。分析：这是一道广为流传的 google 面试题。

int one_appear_count(int n);

思路 1. 遍历 1~n，统计出现 1 的个数；n 足够大时，效率很低思路 2. 分析规律

搜索旋转排序数组¶

整数数组 nums 按升序排列，数组中的值互不相同。

在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标从 0 开始计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

给你旋转后的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

示例 1：

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

示例 2：

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1