不是主流思想里的解题角度和思路的合集
422 数组中重复的数字：

时间复杂度O(n)，空间复杂度O(1)，仅使用常量额外空间的算法解决此问题。（输入输出的空间不算额外的空间，以列表或者其他任何形式存储的输出空间）
要点：
- 【用我查别人】假如没有重复的数字，那么由题意，每个数字都会对应唯一的下标（用数字作下标）；而现在有重复的数字，用数字做下标会指向同一个地址；若该地址被访问过第一次，并标记，访问第二次时发现有标记就可以表明该索引重复，means列表内有重复的数字，把该索引值存起来即可。
- 【绝对值的使用】标记，把访问过的值改为绝对值，特点：便于检查标记且通用，因为数组里的数原本都是正数，要使用原本的数字只需要使用原位置上数字的绝对值，若要边遍历边修改原数组数，要能够在遍历到之时还原该数
ppt链接

@遍历时改变当前指向元素后跳过改变值的问题

例题：41.缺失的第一个正整数（从1–n+1）

原地哈希法（java代码示例）

原本的逻辑是：把数字为 **num **的元素放置到 **num-1 **的下标上, 遍历指针目前为 **i **

最后产生的结果是改变了数组内数的顺序，使得能够归位的数字归到其该对应的位置上

把数字为 **num **的元素放置到 **num-1 **的下标上，大于数组长度的数以及小于0的数不排序（用这些数作索引值，超出索引范围），并且假若该元素已经归位也不用进行排序由于某个元素被交换到当前指针 i 的位置上，所以改为while会让这个位置上的数继续进行判断并一直调整位置，直到 i 位置上的数在合适的位置为止，所以把 if 改为 while

274. H 指数

我们需要找到满足条件「引用次数至少为次的篇论文」中的最大值。

H的范围[0,len(citations)],并且是左闭右闭区间
H要满足的条件，有h篇论文发表的次数至少被引用h次，也就是说，可以先假设h为某个数，再检查是否有**h个数字>= h: **
1. 假设h的值
2. 找到h个数字
3. 假设成立，得到h
一题多解
1. 暴力解法（时间O(n^2)）：从0开始假设h，每次假设都要遍历一遍数组统计看是否能得到h个数字
2. 二分查找（时间O(nlogn)）：由于H存在的范围刚好是数组长度，要_查找的数又已经有特定的条件限定_，可以用二分查找找到这个数H，开始可以假设h为数组中间的数mid;

假如符合条件的数的个数x<mid,（mid偏大）mid–，看向左区间； x>mid,mid偏小，mid++，看向右区间；

用 mid 来代表随便瞎猜的一个数组下标，下标自然就是有序的，但每次都要遍历一遍数组来查找符合>=h的数有多少个

降序核对(时间O(n))：
1. 把数组降序排列，先假设h=0，若最大的数citations[0] （实现方法不同）,则 h-=1 ，一旦找到，由于从最大的数（len(citiations)）开始往下找，则第一个找到的数就是h
```
def HIndex(citations):
 citations.sort(reverse=True)
 for i,t in enumerate(citations):
 # [4,4,3,1,0],当i=2指向t=3时，说明前面已经有3（i+1）个大于等于3的数     
 # i继续向后走一位，自主+1时，一定能满足条件，于是此时输出i
  if i>=t:return i  
 return len(citations)
```
  要确定一个人的h指数非常容易，到SCI网站，查出某个人发表的所有SCI论文，让其按被引次数从高到低排列，往下核对，直到某篇论文的序号大于该论文被引次数

1. 两数之和

边查找边把数据存入数据结构中

算法题合集（简单收录）

422 数组中重复的数字：

@遍历时改变当前指向元素后跳过改变值的问题

原地哈希法（java代码示例）

274. H 指数

1. 两数之和

CATALOG

FEATURED TAGS

FRIENDS