文创产品设计包括哪些方面_yy直播是个什么样的平台_百度指数趋势_百度爱采购竞价推广

AcWing 13. 找出数组中重复的数字 - AcWing

一、题目：13. 找出数组中重复的数字

思想：

主要就是让nums[i] = i; 遍历nums 动态数组

代码

class Solution {
public:int duplicateInArray(vector<int>& nums) {int n = nums.size();// 获取nums全部值for(auto x : nums) if(x<0 || x>=n) return -1;// 遍历数组for(int i = 0; i < n; i ++) {while(nums[i]!=nums[nums[i]]) swap(nums[i],nums[nums[i]]);if(i!=nums[i]) return nums[i];}return -1;}
};

二、题目：14.不修改数组找重复数字

思想：

抽屉原理＋分治思想：

抽屉原理：题目n+1个数，相当于n+1个苹果，均在1-n的范围，相当于有n个抽屉。全部苹果放入抽屉，那么一定会有一个抽屉出现两个苹果。

通过分治的思想，划分区间，苹果数大于抽屉数即在区间内的数大于区间长度。不断查找此区间，缩小范围，最后长度为1的区间就是重复数字了。

代码：

class Solution {
public:int duplicateInArray(vector<int>& nums) {int l = 1, r = nums.size()-1;while(l<r) {// 区间划分int mid = l+r>>1;int num = 0;//num为区间[l,mid]的个数for(auto x : nums) num+= x>=l && x<=mid;if(num>mid-l+1) r = mid;else l = mid+1;}return l;}
};