顿搜
飞过闲红千叶，夕岸在哪
类目归类
数组操作——算法设计 · 篇二
08/11
一、特殊数组中的查找
GitHub地址：特殊数组中的查找(经典).cpp
- ①、数组中只有一个数出现了一次，其他都出现了两次，找到这个出现一次的数字
将整个数组中的整数进行异或，最后得到的结果就是所要找的数
- ②、数组中有两个数出现了一次，其他都出现了两次 这两个数分别是什么
1、将整个数组中的整数进行异或
2、找到异或结果中第一个为1的位，若第j位为1，说明这两个数字在第j位上是不同。
3、根据这个位将原数组分成两类。对每一类进行全体异或，得到的数就是要求的数字
- ③、数组中只有一个数出现了一次，其他都出现了三次，找出这个数
1、通过某一位的值将数组分为两部分，其中一部分包含了待找的数，另一部分不包含
2、包含待找的数的那一部分的数字个数对3取模余1，另一部分对3取模余0
3、对包含待找的数的那一部分，用同样的方法再进行分割，直到分割到最后只剩一个数
## 二、设置二维数组中的元素值 > GitHub地址：设置二维数组中的元素值.cpp + ①、二维数组中，如果某一个元素的值为0，将其所在的行和列所有元素都置为0，尽可能小的空间复杂度 > 1、判断第一行是否有值为0 的元素，若有，则设标志firstLine为1 > 2、判断第一列是否有0的元素，若有，则设标志firstRow为1 > 3、遍历二维数组（第二行第二列开始），遇到0则将第一行和第一列的值先设置好 > 4、根据第一行第一列的值，再次遍历二维数组，更新其他值 > 5、根据firstLine和firstRow更新第一行和第一列的值
## 三、第 K 大问题 > GitHub地址：第 K 大问题（经典）.cpp + ①、查找一个数组中的第K大的元素 > 1、随机选择一个支点 int pivot = low+rand()%(high-low+1);并交换到第一个元素 > 2、每遍历一次，把较大的放到数组的左边，并记录比关键点大的数的个数为count，即交换次数 > 3、遍历完后，将关键点放在左右两部分的分界点 > 4、更具count计数判断第K大的数在哪部分，重复上述过程 + ②、查找最小的K个数 > 1、建立最大堆（元素个数为k），然后依次将剩余的元素与堆顶元素进行比较 > 2、如果该元素小于堆顶元素，则剔除堆顶元素，并将该元素插入到最大堆中 > 3、遍历完后，最大堆中的数据就是要找的k的最小数
## 四、逆序对 > GitHub地址：数组中的逆序对（归并思想）.cpp 利用归并的思想 > 1、将数组二分，然后对二分的数组归并 > 2、归并的过程中，若是取第二部分的元素，则累积记录该元素到目标元素的位置差 > 3、最终总的位置差就是逆序对的个数。
