C/C++教程

C++牛客网编程(五)

本文主要是介绍C++牛客网编程(五),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

描述

在一个长度为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];
        }
    }

};

这篇关于C++牛客网编程(五)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!