无序数组去重算法

无序数组去重算法的复杂度是O(n²)。

代码如下,首先进行外层循环，复杂度O(n)，然后查找这个元素之前的元素中有没有重复的，复杂度O(n)，如果有就删除，复杂度O(1)，没有就下一个元素，复杂度O(1)。加起来复杂度O(n²)。

完整代码在github上面，只需要clone下来执行composer install然后执行 php artisan test:unsortDeduplicate 就可以看到结果了

    /**
     * Execute the console command.
     *
     * @return mixed
     */
    public function handle()
    {
        $a = [4,5,4,3,8,6,6,10,34,10,4];
        dump($a);
        $i = 1;
        $len = count($a);
        dump("长度:".$len);
        while ($i < $len) { //循环全部数据
            //在整个数组中寻找这个值，如果找到了就删除他，如果没找到就下一个
            $preIndex = $this->find($i, $a);
            if ($preIndex!==false) {unset($a[$preIndex]);}
            else $i++;
        }
        dd($a);
    }

    private function find($i, array $a) {
        $index = 0;
        //循环从0到这个下标
        while ($index < $i) {
            //不存在说明被删除了
            if (!array_key_exists($index, $a)) {$index++;continue;}
            //如果找到了返回下标
            if ($a[$i] == $a[$index]) return $index;
            else $index++;
        }
        return false;
    }

作者：Grey

原文地址: 求无序数组求第K大的数

问题描述

无序数组求第K大的数，其中K从1开始算。

例如：[0,3,1,8,5,2]这个数组，第2大的数是5

OJ可参考：LeetCode 215. Kth Largest Element in an Array

堆解法

设置一个小根堆，先把前K个数放入小根堆，对于这前K个数来说，堆顶元素一定是第K大的数，接下来的元素继续入堆，但是每入一个就弹出一个，最后，堆顶元素就是整个数组的第K大元素。代码如下：

class Solution {
    public static int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        for (int i = 0; i < k; i++) {
            heap.offer(nums[i]);
        }
        for (int i = k; i < nums.length;i++) {
            heap.offer(nums[i]);
            heap.poll();
        }
        return heap.peek();
    }
}

由于每次堆需要承担logK的调整代价, 所以这个解法的时间复杂度为O(N*logK)

改进快排算法

快速排序中，有一个partition的过程, 这个过程随机选择数组中的一个数，假设叫pivot，这个过程主要作用是将数组的l...r区间内的数：

• 小于pivot的数放右边

• 大于pivot的数放左边

• 等于pivot的数放中间

返回两个值，一个是左边界和一个右边界，位于左边界和右边界的值均等于pivot，小于左边界的位置的值都大于pivot，大于右边界的位置的值均小于pivot。简言之：如果要排序，pivot这个值在一次partition以后，所在的位置就是最终排序后pivot应该在的位置。

所以，如果数组中某个数在经历上述partion之后正好位于K-1位置，那么这个数就是整个数组第K大的数。

快排改进算法完整代码如下：

class Solution {
       public static int findKthLargest(int[] nums, int k) {
        return process(nums, 0, nums.length - 1, k - 1);
    }

    // arr 在L...R范围内，如果要从大到小排序，请返回index位置的值
    private static int process(int[] arr, int L, int R, int index) {
        if (L == R) {
            return arr[R];
        }
        int pivot = arr[L + (int) (Math.random() * (R - L + 1))];
        int[] range = partition(arr, L, R, pivot);
        if (index >= range[0] && index <= range[1]) {
            return pivot;
        } else if (index < range[0]) {
            return process(arr, L, range[0], index);
        } else {
            return process(arr, range[1], R, index);
        }
    }

    public static int[] partition(int[] arr, int L, int R, int pivot) {
        int less = L - 1;
        int more = R + 1;
        while (L < more) {
            if (arr[L] > pivot) {
                swap(arr, L++, ++less);
            } else if (arr[L] == pivot) {
                L++;
            } else {
                swap(arr, L, --more);
            }
        }
        return new int[]{less + 1, more - 1};
    }
    
    public static void swap(int[] nums, int t, int m) {
        int tmp = nums[m];
        nums[m] = nums[t];
        nums[t] = tmp;
    }
}

其中process方法表示：nums在L...R范围上，如果要排序（从大到小）的话，请返回index位置的值。

int pivot = nums[L + (int) (Math.random() * (R - L + 1))];

这一行表示随机取一个值pivot出来，用这个值做后续的partition操作，如果index恰好在pivot这个值做partition的左右边界范围内，则pivot就是排序后第index+1大的数(从1开始算)。

bfprt算法

brfpt算法和改进快排算法主流程上基本一致，只是在选择pivot的时候有差别，快排改进是随机取一个数作为pivot, 而bfprt算法是根据一定的规则取pivot，核心代码为：

public class LeetCode_0215_KthLargestElementInAnArray {
    ......
    // nums在L...R范围上，如果要排序（从大到小）的话，请返回index位置的值
    public static int bfprt(int[] nums, int L, int R, int index) {
        if (L == R) {
            return nums[L];
        }
        //int pivot = nums[L + (int) (Math.random() * (R - L + 1))];
        int pivot = medianOfMedians(nums, L, R);
        int[] range = partition(nums, L, R, pivot);
        if (index >= range[0] && index <= range[1]) {
            return pivot;
        } else if (index < range[0]) {
            return bfprt(nums, L, range[0] - 1, index);
        } else {
            return bfprt(nums, range[1] + 1, R, index);
        }
    }
    ......
}

其中

int pivot = medianOfMedians(nums, L, R);

就是bfprt算法最关键的步骤，mediaOfMedians这个函数表示：

将num分成每五个元素一组，不足一组的补齐一组，并对每组进行排序(由于固定是5个数一组进行排序，所以排序的时间复杂度O(1))，取出每组的中位数，组成一个新的数组， 对新的数组求其中位数，这个中位数就是我们需要的值pivot。

    public static int medianOfMedians(int[] arr, int L, int R) {
        int size = R - L + 1;
        int offSize = size % 5 == 0 ? 0 : 1;
        int[] mArr = new int[size / 5 + offSize];
        for (int i = 0; i < mArr.length; i++) {
            // 每一组的第一个位置
            int teamFirst = L + i * 5;
            int median = getMedian(arr, teamFirst, Math.min(R, teamFirst + 4));
            mArr[i] = median;
        }
        return bfprt(mArr, 0, mArr.length - 1, (mArr.length - 1) / 2);
    }

    public static int getMedian(int[] arr, int L, int R) {
        Arrays.sort(arr, L, R);
        return arr[(R + L) / 2];
    }

注：mediaOfMedians方法中最后一句：

return bfprt(mArr, 0, mArr.length - 1, (mArr.length - 1) / 2);

就是利用bfprt算法拿整个元素中间位置的值。

关于bfprt算法的两个问题

1. 为什么是5个一组

2. 为什么严格收敛到O(N)

请参考：

BFPRT算法原理

BFPTR算法详解+实现+复杂度证明

三种解法复杂度分析

相关题目

寻找两个正序数组的中位数

OJ见：LeetCode 4. Median of Two Sorted Arrays

代码见：LeetCode_0004_MedianOfTwoSortedArrays

第K小的数值对

长度为N的数组arr，一定可以组成N^2个数值对。例如arr = [3,1,2]，数值对有(3,3) (3,1) (3,2) (1,3) (1,1) (1,2) (2,3) (2,1) (2,2)，也就是任意两个数都有数值对，而且自己和自己也算数值对。数值对怎么排序？规定，第一维数据从小到大，第一维数据一样的，第二维数组也从小到大。所以上面的数值对排序的结果为：(1,1)(1,2)(1,3)(2,1)(2,2)(2,3)(3,1)(3,2)(3,3), 给定一个数组arr，和整数k，返回第k小的数值对。

代码见：Code_0015_KMinPair

更多

算法和数据结构笔记

参考资料

程序员代码面试指南（第2版）

算法和数据结构体系班-左程云

BFPRT算法原理

BFPTR算法详解+实现+复杂度证明

1.无序数组找中位数

1. 思路一
   把无序数组排好序，取出中间的元素
   时间复杂度 采用普通的比较排序法 O(N*logN)
   如果采用非比较的计数排序等方法， 时间复杂度 O(N), 空间复杂度也是O(N).

2. 思路二
   （1）将前(n+1)/2个元素调整为一个小顶堆
   （2）对后续的每一个元素，和堆顶比较，如果小于等于堆顶，丢弃之，取下一个元素。 如果大于堆顶，用该元素取代堆顶，调整堆，取下一元素。重复2.2步
   （3）当遍历完所有元素之后，堆顶即是中位数。
   注：如果数组元素的个数是奇数，取数组前(size+1)/2个元素建堆，如果是偶数则取前 size/2 个元素建堆。但如果是数据流，数据个数是动态变动的，则应采用小根堆+大根堆的办法，具体见本文第5点介绍。

3. 思路三
   找中位数也可以用快排分治的思想。具体如下：
   （1）任意挑一个元素，以改元素为支点，划分集合为两部分，如果左侧集合长度恰为 (n-1)/2，那么支点恰为中位数。如果左侧长度<(n-1)/2, 那么中位点在右侧，反之，中位数在左侧。
   （2）进入相应的一侧继续寻找中位点。
   注：可参考快排思想实现Top K

拓展：查找N个元素中的第K个小的元素，假设内存受限，仅能容下K/4个元素
分趟查找：

1. 第一趟，用堆方法查找最小的K/4个小的元素，同时记录剩下的N-K/4个元素到外部文件。
2. 第二趟，用堆方法从第一趟筛选出的N-K/4个元素中查找K/4个小的元素，同时记录剩下的N-K/2个元素到外部文件。
3. …
4. 第四趟，用堆方法从第一趟筛选出的N-K/3个元素中查找K/4个小的元素，这是的第K/4小的元素即使所求。

https://blog.csdn.net/zdl1016/article/details/4676882

2.将十进制数字转化为X 进制的字符串

//将十进制数转化为X进制字符串 
string trans(int num, int base){
	string str;
	while(num > 0){
		if(num % base < 10)
			str += num % base + '0';
		else
			str += num % base - 10 + 'A';
		num = num / base;
	}
	reverse(str.begin(),str.end());
	
	return str;
}

3.找出字符串中第k次出现的字符

1. 思路一
   遍历这个字符串（缺点是要对这个字符串查找好多次）
2. 思路二
   (1) 先创建一个数组然后这个数组你就放成256个元素。
   (2) 把这个字符串转化成ASCLL码进行查找。（因为ASCLL码的范围比较小）
   (3) 当我们发现字符串中出现a（a的ASCLL为97）的时候，我们可以把刚才256个元素中下边为97的元素的值加一。

char find_first_K(string str, int K)
{
	int count[256] = { 0 };
	for (char ch : str) ++count[ch];

	for (char ch : str) {
		if (count[ch] == K)
			return ch;
	}

	return '0';
}

5.找出数据流中的中位数

注意：始终保证小根堆A中元素个数不少于大根堆B中的元素个数，即A、B元素相等时，将B中最大元素加入A，否则将A中最小元素加入B，来维持元素个数平衡。

class MedianFinder {
private:
    priority_queue<int,vector<int>, greater<int>> A;    //小根堆
    priority_queue<int,vector<int>, less<int>> B;       //大根堆

public:
    //插入新元素
    void addNum(int num) {
        if(A.size()==B.size()){ //把B中最大元素加入到A
            B.push(num);
            A.push(B.top());
            B.pop();
        }else{                  //把A中最小元素加入到B
            A.push(num);
            B.push(A.top());
            A.pop();
        }
    }
    
    //查找当前中位数
    int findMedian() {
        return A.size()==B.size()?(A.top()+B.top())/2.0:A.top();
    }
};

6.英文字符串流和中文字符串流如何分词

一种对英文字符串进行分词的方法：https://d.wanfangdata.com.cn/periodical/jsjyyyj200707016

字典与统计相结合的中文分词方法：https://d.wanfangdata.com.cn/periodical/xxwxjsjxt200609039

暴力方法：

1. 英文分词：根据字符串中的空格、标点符号进行分词。
2. 中文分词：固定两个字为一词进行拆分。

7.10亿QQ号去重

1. 内存够的情况

分段、map、多线程。

1. 分段：哈希分桶，根据哈希值对桶数目取模得到对应桶号。
2. map：需要计数采用unordered_map去重；不需要计数采用set去重。
3. 多线程：将数据进行哈希分桶之后，各桶内map的去重可以采用多线程执行。

2. 内存不够的情况

思路一：bitmap

位图bitmap：每个int数字只用一个比特位来做标记

位图的操作（算法）基本依赖于下面3个元操作：

set_bit(char x, int n); //将x的第n位置1，可以通过x |= (1 << n)来实现

clr_bit(char x, int n); //将x的第n位清0，可以通过x &= ~(1 << n)来实现

get_bit(char x, int n); //取出x的第n位的值，可以通过(x >> n) & 1来实现

比如，要对数字int x = 1848105做标记，就可以调用set_bit(bit_map[x/8], x%8);

除法看做求“组编号”，x/8即是 以8个位为一个小组，分组到编号为idx = x/8的bit_map元素中，然后在组内偏移lft = x%8个比特位。

10亿数字(int 32位)：10^8 * 32 / 8 = 40亿字节 / 1024 ≈ 400万 KB / 1024 ≈ 4000 MB / 1024 ≈ 4 GB
int 32位所需bitmap大小：2^32 / 8 = 2^29 字节 / 1024 = 2^19 KB / 1024 = 2^9 MB = 512 MB

10亿数字(long long 64位)：4 GB * 2 = 8GB
long long 64位所需bitmap大小：2^64 / 2^23 = 2^41 MB / 1024 = 2^31 GB / 1024 = 2^21 TB / 1024 = 2048 PB = 2 EB

https://www.cnblogs.com/zhanghaiba/p/3594559.html

思路二：多路归并排序

问题：如何给100亿个数字排序？

注：100亿个 int 型数字放在文件里面大概有 37.2GB

1. 把这个37GB的大文件，用哈希分成1000个小文件，每个小文件平均38MB左右（理想情况），把100亿个数字对1000取模，模出来的结果在0到999之间，每个结果对应一个文件，所以我这里取的哈希函数是 h = x % 1000，哈希函数取得”好”，能使冲突减小，结果分布均匀。
2. 按各输入文件中下一个读到的元素的大小构造一个输入流最小堆.
3. 从堆顶文件里读一个元素并写入输出文件.
4. 同时按读的那个文件的下一个元素的值调整堆.
5. 若第3步已到达文件结尾.则从堆中删除该输入流.
6. 如果堆中还有元素. 回到第2步.

3. 外存不够的情况

考虑是不是可以进行分布式处理

待查~