解法1：二分查找
对于示例[1,3,4,2,2]，target=2，我们用cnt表示元素统计数组，其中cnt[i]表示nums中值小于等于i的元素个数。通过分析可得，对于[1, target-1]中元素i，其cnt[i]<=i，对于[target, n]中元素，其cnt[j]>j。因此我们可以得到以下新的数组：
由于cnt数组是递增的，所以我们可以使用二分查找来求解，目标是找到第一个满足cnt[i]>i的元素。
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
result = 0
while left <= right:
mid = (left+right) // 2
count = 0
# 计算位置mid的cnt[mid]值
for i in range(len(nums)):
if nums[i] <= mid:
count += 1
if count > mid:
right = mid-1
result = mid
else:
left = mid + 1
return result
解法2：快慢指针（可对照141. 环形链表，142. 环形链表 II进行学习）
思路：
题目设定的问题是 N+1 个元素都在 [1,n] 这个范围内，且具有重复值，根据其特殊性，我们可以将数组转换成一个有环图来解决。因此寻找重复值的目标转变为求解环的入口值。
图的构造方式如下：
从理论上讲，数组中如果有重复的数，那么就会产生多对一的映射，这样，形成的链表就一定会有环路了，
求解步骤：初始化一个慢指针和一个快指针，移动步长分别为1和2，假设从起点到入口的距离为a，从入口到慢指针与快指针第一次相遇位置的距离为b，环的长度为L，从相遇距离到入口的距离为c。分析可得：
第一次相遇：慢指针位移：a+b，快指针位移：2(a+b)=a+b+kL （其中k为快指针遍历环的次数，至少为1），L=b+c
由此我们可以推导得知 a = kL-b = (k-1)L + c，其中a为起点到入口的距离，同时也是慢指针从起点到环入口所移动次数。分析可得，若新建一个finder指针，从起点以慢指针速度位移至入口。同时慢指针继续位移，位移距离为(k-1)L+c，总位移距离为a+b+(k-1)L+c=a+kL，正好回到入口处与finder指针相遇，相遇点就是最终答案。所以总的步骤就是求解两次相遇过程，作为结果返回第二次相遇点。
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
low, fast = 0, 0
low = nums[low]
fast = nums[nums[fast]]
# 第一次相遇
while low != fast:
low = nums[low]
fast = nums[nums[fast]]
# print(low, fast)
finder = 0
# 第二次相遇
while finder != low:
finder = nums[finder]
low = nums[low]
return finder
键盘行
解法：遍历
我们为每一个英文字母标记其对应键盘上的行号，然后检测字符串中所有字符对应的行号是否相同。
- 我们可以预处理计算出每个字符对应的行号。
- 遍历字符串时，统一将大写字母转化为小写字母方便计算。
class Solution:
def findWords(self, words: List[str]) -> List[str]:
ans = []
# abc...xyz所在键盘行
rowIdx = "12210111011122000010020202"
for word in words:
idx = rowIdx[ord(word[0].lower()) - ord('a')]
if all(rowIdx[ord(ch.lower()) - ord('a')] == idx for ch in word):
ans.append(word)
return ans
