在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的,但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如,如果输入长度为7的数组[2,3,1,0,2,5,3],那么对应的输出是2或者3。存在不合法的输入的话输出-1
数据范围:0≤n≤10000
进阶:时间复杂度O(n) ,空间复杂度O(n)
思路:设置另外一个数组作为个数标志,直到大于1就输出
int duplicate(vector<int>& numbers) { int count=numbers.size(); int a[100002]={}; for(int i=0;i<count;i++){ if(numbers[i]>10000||numbers[i]<0){//如果不合法输入 return -1; } a[numbers[i]]++; if(a[numbers[i]]>1){//如果超过两个 return numbers[i]; } } return -1; }
在看别人的做法中有几个特别需要关注的
1. 可以用暴力解法,做两个N次循环,第一个定要比较的树,第二个遍历后面所有的数,但时间复杂度为o(n^2),空间复杂度为o(1)
2. 可以先排序后遍历,排序可以直接用系统函数sort,时间复杂度为o(nlogn)
3. 用set集合,思想和我的类似,查看数是否在set集合中,如果在就输出,不在就插入set集合
set集合是c++ stl库中自带的一个容器,set具有以下两个特点:
* set中的元素都是排好序的
* set集合中没有重复的元素
int duplicate(vector<int>& numbers) { set<int> s; for(int i=0;i<numbers.size();i++){ if(s.count(numbers[i])>0) return numbers[i]; else s.insert(numbers[i]); } return -1; }
另外一个同学在set方法上有不同的想法:
一次循环依次遍历数组,并与查询hash表(hash表采用unordered_set容器,而不要采用set,unordered_set底层使用的vector+list开链法,理论查询时间O(1),set底层采用红黑树,查询时间稳定log(n)):
(1)hash表存在该数字,结束返回结果;
(2)hash表不存在该数字,将该数字加入hash表中;
循环结束代表未找到,返回-1;
4.这个同学还运用了原地hash,不再设置另外一个数组,而是修改本身数组,降低空间复杂度
可以利用swap()函数使numbers里面的数对应到数组的下标上。
遍历整个数组:
1、当numbers[i]等于下标i,判断下一个下标是否对应;
2、当numbers[i]不等于下标i
(1)numbers[i]==numbers[numbers[i]],此时对应下标i的numbers[i]已经对应,那么出现重复数字;
(2)否则swap(numbers[numbers[i]],numbers[i]);
3、遍历结束都未发现重复数字,则返回-1;
int duplicate(vector<int>& numbers) { // write code here for(int i=0;i<numbers.size();){ if(i==numbers[i])++i;//当numbers[i]等于下标i,判断下一个下标是否对应; else { if(numbers[numbers[i]] == numbers[i]){ return numbers[i]; }else{ std::swap(numbers[numbers[i]],numbers[i]);//交换使numbers[i]与下标i对应起来; } } } return -1; }
在数组中的两个数字,如果前面一个数字大于后面的数字,则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P mod 1000000007
数据范围: 对于 的数据, size≤104
对于 100%的数据, size≤105
数组中所有数字的值满足 0≤val≤10000000
要求:空间复杂度 O(n),时间复杂度 O(nlogn)
题目保证输入的数组中没有的相同的数字
思路:首先一开始想的是利用set中可以自动排序的特点,遍历数组时将数加入到set中,计算加入前里面有多少大于它的数,就是有多少个逆排序数。set插入时间复杂度为o(logn),distance时间复杂度为o(n),所以总体还是o(n^2),超过了要求。
int InversePairs(vector<int> data) { set<int> s; int num=0,tmp,total=data.size(); for(int i=0;i<total;i++){ if(i==0) s.insert(data[i]); else{ tmp=s.size()-distance(s.begin(),s.upper_bound(data[i])); num+=tmp; s.insert(data[i]); } } return num%1000000007; }
于是看到其它同学使用了归并排序,他的图很清晰
时间复杂度为O(nlogn)
class Solution { private: const int kmod = 1000000007; public: int InversePairs(vector<int> data) { int ret = 0;//逆排序数组的个数 // 在最外层开辟数组 vector<int> tmp(data.size()); merge_sort__(data, tmp, 0, data.size() - 1, ret); return ret; } void merge_sort__(vector<int> &arr, vector<int> &tmp, int l, int r, int &ret) { if (l >= r) { return; } int mid = l + ((r - l) >> 1);//右移一位,相当于除以2 merge_sort__(arr, tmp, l, mid, ret);//分,左边子数组 merge_sort__(arr, tmp, mid + 1, r, ret);//分,左边子数组 merge__(arr, tmp, l, mid, r, ret);//合 } void merge__(vector<int> &arr, vector<int> &tmp, int l, int mid, int r, int &ret) { int i = l, j = mid + 1, k = 0; while (i <= mid && j <= r) { if (arr[i] > arr[j]) {//如果左边大于右边,有逆序 tmp[k++] = arr[j++]; ret += (mid - i + 1); ret %= kmod; } else { tmp[k++] = arr[i++];//没有逆序 } } while (i <= mid) {//如果左边子数组有剩余 tmp[k++] = arr[i++]; } while (j <= r) {//如果右边子数组有剩余 tmp[k++] = arr[j++]; } for (k = 0, i = l; i <= r; ++i, ++k) {//将原来的数组改变成排好序的 arr[i] = tmp[k]; } } };