关于C++数组中重复的数字

目录
  • 1、题目描述
    • 1.1 方法一:排序
    • 1.2 方法二:哈希表
    • 1.3 方法三:数组位置交换
  • 2、题目升级
    • 2.1 方法一:哈希表
    • 2.2 方法二:辅助数组
    • 2.3 方法三:二分查找

1、题目描述

找出数组中重复的数字。在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。

请找出数组中任意一个重复的数字。

题目示例:

  • 输入:[2, 3, 1, 0, 2, 5, 3]
  • 输出:2 或 3

1.1 方法一:排序

先对数组进行排序
此时从头到尾扫一遍数组就可以了
时间复杂度 O ( l o g 2 n ) O(log_2n) O(log2​n)

代码示例:

int repeatNum(vector<int>& v){
    if(v.empty()) return -1;
    int len = v.size();
    sort(v.begin(), v.end());
    for(int i = 1; i < len; i++){
        if(v[i] == v[i-1]){
            return v[i];
        }
    }
    return -1;
}

1.2 方法二:哈希表

  • 从头到尾扫一遍数组
  • 每扫到一个数字,判断哈希表里是否包含了该数字
  • 如果还没有,就把它加入哈希表中
  • 如果已经存在该数字,就找到了一个重复的数字。

时间复杂度 O ( n ) O(n) O(n) 、空间复杂度 O ( n ) O(n) O(n) ,提高时间效率是以创建一个 O ( n ) O(n) O(n) 的哈希表为代价的。

代码示例:

int repeatNum(vector<int>& v){
    if(v.empty()) return -1;
    map<int, int> m;
    for(int i = 0; i < v.size(); i++){
        if(m[v[i]]) return v[i];
        else m[v[i]]++;
    }
    return -1;
}

1.3 方法三:数组位置交换

  • 从头到尾扫描数组
  • 当扫描的数组下标为 i 时,判断i这个位置的数字 (m) 是否等于 i 本身
  • 若是则扫描下一个数字
  • 若不是则判断 m 和 下标为 m 的数字是否相同 (v[i] == v[v[i]])
  • 若相同则返回,循环结束
  • 若不同则把第 i 个数字 (m) 和 第 m 个数字交换
  • 然后重复这个过程,直至循环结束

时间复杂度为 O ( n ) O(n) O(n) ,空间复杂度为 O ( 1 ) O(1) O(1)

代码示例:

int repeatNum(vector<int>& v){
    if(v.empty()) return -1;
    for(int i = 0; i < v.size(); ++i){
        if(v[i] < 0 || v[i] > v.size()-1) // 数字必须在 0 ~ n-1 之间
            return -1;
    }

    for(int i = 0; i < v.size(); ++i){
        while(v[i] != i){
            if(v[i] == v[v[i]]) return v[i];
            swap(v[i], v[v[i]]);
        }
    }
    return false;
}

2、题目升级

长度为 n+1 的数组,所有的数都在 1 ~ n 的范围内,因此数组中至少有一个数字是重复的。找出数组中 任意一个 重复的数字,但 不能修改输入的数组。

题目示例:

  • 输入:[2, 3, 5, 4, 3, 2, 6, 7]
  • 输出:2 或 3

2.1 方法一:哈希表

方法同上:

int repeatNum(vector<int>& v){
    if(v.empty()) return -1;
    map<int, int> m;
    for(int i = 0; i < v.size(); i++){
        if(m[v[i]]) return v[i];
        else m[v[i]]++;
    }
    return -1;
}

2.2 方法二:辅助数组

  • 创建一个长度为 n+1 的辅助数组,然后逐一的把原数组的每个数字复制到辅助数组中
  • 若原数组中 被复制的数字 是 m,则把它复制到辅助数组中下标为 m 的位置

时间复杂度为 O ( n ) O(n) O(n) ,空间复杂度为 O ( n ) O(n) O(n)

代码示例:

int repeatNum(vector<int>& v){
    int len = v.size();
    vector<int> v1(len);
    for(int i = 0; i < len; ++i){
        if(v1[v[i]]) return v1[v[i]];
        else v1[v[i]] = v[i];
    }
    return -1;
}

2.3 方法三:二分查找

将 1 ~ n 的数字从中间的数字 分成两部分,即分成 1 ~ m m+1 ~ n

  • 若 1 ~ m 的数字,在整个数组上的数目超过 m,即超过该区间的长度,那么这一半的区间里一定包含重复的数字
  • 否则,另一半 m+1 ~ n 区间里一定包含重复的数字

继续把包含重复数字的区间一分为二,直到找到一个重复的数字

时间复杂度为 O ( n l o g n ) O(nlog_n) O(nlogn​),空间复杂度为 O ( 1 ) O(1) O(1)

代码示例:

int countRange(vector<int>& v, int sz, int start, int end){
    if(v.empty()) return 0;

    int count = 0;
    for(int i = 0; i < sz; ++i){
        if(v[i] >= start && v[i] <= end){
            ++count;
        }
    }
    return count;
}

int getrepeat(vector<int>& v){
    if(v.empty()) return -1;

    int sz = v.size();
    int start = 1, end = sz-1;
    while(end >= start){
        int mid = start + ((end-start)>>1);
        int count = countRange(v, sz, start, mid);
        if(end == start){
            if(count > 1) return start;
            else break;
        }
        if(count > (mid - start + 1)) end = mid;
        else start = mid + 1;
    }
    return -1;
}

测试代码:

bool duplicate(vector<int>& v, int **res){
    if(v.empty()) return false;
    for(int i = 0; i < v.size(); ++i){
        if(v[i] < 0 || v[i] > v.size()-1)
            return false;
    }

    for(int i = 0; i < v.size(); ++i){
        while(v[i] != i){
            if(v[i] == v[v[i]]) {
                *res = &v[i];
                return true;
            }
            swap(v[i], v[v[i]]);
        }
    }
    return false;
}

int main(){
    int arr[] = {2, 3, 5, 4, 3, 2, 6, 7};
    vector<int> v(arr, arr+8);  // 这种赋值方式不会导致vector自动扩展内部大小

    int* res = nullptr;
    if(duplicate(v, &res)) cout << *res << endl;
    else cout << '0' << endl;
    //cout << repeatNum(v) << endl;
    /*
    for(int i = 0; i < v.size(); i++){
        if(i == 0) cout << v[i];
        else cout << ' ' << v[i];
    }
    cout << endl;

    for(auto a : v){    // 有两个警告(auto是C++_11的扩展)
        cout << a << ' ';
    }
    */
    return 0;
}

到此这篇关于关于C++数组中重复的数字的文章就介绍到这了,更多相关C++数组中重复数字内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

注:文章转自微信公众号:Coder梁(ID:Coder_LT)

(0)

相关推荐

  • C++实现LeetCode(26.有序数组中去除重复项)

    [LeetCode] 26. Remove Duplicates from Sorted Array 有序数组中去除重复项 Given a sorted array nums, remove the duplicates in-place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this

  • C++实现LeetCode(80.有序数组中去除重复项之二)

    [LeetCode] 80. Remove Duplicates from Sorted Array II 有序数组中去除重复项之二 Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length. Do not allocate extra space for another array, you mus

  • C语言 数组中重复的数字分析及方法

    C语言 数组中重复的数字解决方法: 题目:在一个长度为n的数组里的所有数字都在0-n-1的 范围内.数组中某些数字是重复的,但是不知道有几个数字重复了,也不知道每个数字重复了几次.请找出数组中任意一个重复的数字.例如,如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出是重复的数字2或者3. 解法1:对于数组进行排序,之后对于已经排序的数组进行遍历便可知道数组中重复的数字. 时间复杂度;O(nlogn); 解法2:建立一个大小为O(N)的哈希表,遍历数组中的元素并判断是否存在于哈

  • Java如何找出数组中重复的数字

    题目描述:找出数组中重复的数字,具体内容如下 在一个长度为n的数组里的所有数字都在 0~n-1的范围内.数组中某些数字是重复的,但不知道有几个数字是重复的,也不知道每个数字重复了几次.请找出数组中任意一个重复的数字.例如:如果输入长度为7的数组{2,3,1,0,2,5,3},那么对应的输出的是重复的数字2或者3 这个面试题是剑指offer中的面试题3,,下面我用java代码实现. 算法步骤: 从头到尾依次扫描数组中的每个数字. 1. 当扫描到下表为i的数字时,首先比较这个数字(用m表示)是不是等

  • 关于C++数组中重复的数字

    目录 1.题目描述 1.1 方法一:排序 1.2 方法二:哈希表 1.3 方法三:数组位置交换 2.题目升级 2.1 方法一:哈希表 2.2 方法二:辅助数组 2.3 方法三:二分查找 1.题目描述 找出数组中重复的数字.在一个长度为 n 的数组 nums 里的所有数字都在 0-n-1 的范围内.数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次. 请找出数组中任意一个重复的数字. 题目示例: 输入:[2, 3, 1, 0, 2, 5, 3] 输出:2 或 3 1.1

  • javascript 删除数组中重复项(uniq)

    可以直接使用的代码:我们修正版 function unique(data){ data = data || []; var a = {}; len = data.length; for (var i=0; i [Ctrl+A 全选 注:如需引入外部Js需刷新才能执行] 下面是进阶教程与说明,喜欢跟深入的朋友可以参考下.首先让我们看下 YUI 是如何处理的: 复制代码 代码如下: var toObject = function(a) { var o = {}; for (var i = 0; i

  • Java实现删除排序数组中重复元素的方法小结【三种方法比较】

    本文实例讲述了Java实现删除排序数组中重复元素的方法.分享给大家供大家参考,具体如下: 题目描述: 给定一个排序数组,在原数组中删除重复出现的数字,使得每个元素只出现一次,并且返回新的数组的长度. 不要使用额外的数组空间,必须在原地没有额外空间的条件下完成. 一:通过ArrayList解决 时间复杂度和空间复杂度都为O(n) ArrayList<Integer> list = new ArrayList<Integer>(); // 去掉数组中重复的元素 public int r

  • Python实现删除排序数组中重复项的两种方法示例

    本文实例讲述了Python实现删除排序数组中重复项的两种方法.分享给大家供大家参考,具体如下: 对于给定的有序数组nums,移除数组中存在的重复数字,确保每个数字只出现一次并返回新数组的长度 注意:不能为新数组申请额外的空间,只允许申请O(1)的额外空间修改输入数组 Example 1: Given nums = [1,1,2], Your function should return length = 2, with the first two elements of nums being 1

  • JS简单去除数组中重复项的方法

    本文实例讲述了JS简单去除数组中重复项的方法.分享给大家供大家参考,具体如下: <!DOCTYPE html> <html lang="zh-cn"> <head> <meta charset="UTF-8"> <title></title> </head> <body> <script> var arr = ["aaa","bb

  • 用JS编写一个函数,返回数组中重复出现过的元素(实例)

    用JS编写一个函数,返回数组中重复出现过的元素,见下面的代码: var arr = [1, 2, 3, 1, 2, 3, 4, 5]; var getRepeat = function (arr) { var obj = {}; for (var i = 0, len = arr.length; i < len; i++) { if (obj[arr[i]] == undefined) { obj[arr[i]] = 1; } else { obj[arr[i]]++; } } for (var

  • php删除数组中重复元素的方法

    几种php删除数组元素方法在很多情况下我们的数组会出现重复情况,那我们删除数组中一些重复的内容怎么办,这些元素必须保持他唯一,所以就想办法来删除它们,下面利用了遍历查询来删除重复数组元素的几种方法. 方法一.完整删除重复数组实例-----删除数组中的一个元素 function array_remove_value(&$arr, $var){ foreach ($arr as $key => $value) { if (is_array($value)) { array_remove_valu

  • JS 清除字符串数组中,重复元素的实现方法

    JS 清除字符串数组中,重复元素的实现方法 <script language="JavaScript"> <!-- var arrData=new Array(); for(var i=0; i<1000; i++) { arrData[arrData.length] = String.fromCharCode(Math.floor(Math.random()*26)+97); } //document.write(arrData+"<br/&g

随机推荐