精华内容
下载资源
问答
  • 不修改数组找出重复的数字 题目: 给定一个长度为 n+1的数组nums,数组中所有的数均在 1∼n的范围内,其中 n≥1。 请找出数组中任意一个重复的数,但不能修改输入...这个题跟上一个找出重复数组元素的很像,当然也...

    不修改数组找出重复的数字

    题目:

    给定一个长度为 n+1的数组nums,数组中所有的数均在 1∼n的范围内,其中 n≥1。

    请找出数组中任意一个重复的数,但不能修改输入的数组。

    样例

    给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。
    
    返回 2 或 3。
    

    思考题:如果只能使用 O(1)O(1) 的额外空间,该怎么做呢?

    题解:

    这个题跟上一个找出重复数组元素的值很像,当然也可以采用上述题的方法,但是,上述方法用到了o(n)的空间,这里的思考要求使用o(1),那么,可以有以下两种解法:

    • 前后指针

      这种解法有一个前提条件,就是数组中一定会存在重复元素,而题中也符合此条件。

      规定一个快指针fast初值为0,一个满指针slow初值为0,快指针先去找数组元素,利用fast=nums[fast];fast = nums[fast];不停的跳,这里有两句,意在比slow快,fast在数组不断的跳,因为会有的重复的,所以fast会出现在一个值或者多个值重复的情况,此时slow = nums[slow];慢指针在后面紧紧跟随,由于fast陷入重复,那么slow就会追上fast,此刻结束循环,找出重复值即可。

      class Solution {
      public:
          int duplicateInArray(vector<int>& nums) {
              int fast = 0;
              int slow = 0;
              while(1){
                  fast=nums[fast];
                  fast = nums[fast];
                  slow = nums[slow];
                  if(fast==slow) break;
              }
              slow = 0;
              while(1){
                  fast = nums[fast];
                  slow=nums[slow];
                  if(fast==slow)return slow;
              }
          }
      };
      
    • 二分法

      这里的二分法与其他的二分法,有些不同,分的不是原来的数组,而是范围,假设范围是17,那么分为两份就是13和47,然后从数组中找到符合两个段的值,以此题为例,符合13的是4个,符合47的也是4个,但是,13只有1,2,3三个元素,此刻却有四个,那么这个范围内的必然有重复的,因此继续范围,直到找到那个重复值。

      class Solution {
          public int duplicateInArray(int[] nums) {
              int len = nums.length;
              if (len == 0) {return -1;}
              int lo = 1;
              int hi = len - 1;
              while(lo <= hi) {
                  int mid = (hi + lo) / 2;
                  int count = 0;
                  for (int n:nums) {
                      if (n >= lo && n <= mid) {
                          count++;
                      }
                  }
                  if (hi == lo) {
                      if (count > 1) {
                          return hi;
                      } else {
                          break;
                      }
                  }
                  if (count > mid - lo + 1) {
                      hi = mid;
                  } else {
                      lo = mid + 1;
                  }
              }
              return -1;
          }
      }
      
    展开全文
  • 找出数组中任意一个重复的数,但不能修改输入数组。 样例 给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。 返回 2 或 3。 思考题:如果只能使用 O(1) 额外空间,该怎么做呢? 题目链接(acWing) 思路: 不能修改...

    给定一个长度为 n+1 的数组nums,数组中所有的数均在 1∼n 的范围内,其中 n≥1。

    请找出数组中任意一个重复的数,但不能修改输入的数组。

    样例

    给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。
    
    返回 2 或 3。
    

    思考题:如果只能使用 O(1) 的额外空间,该怎么做呢?

    题目链接(acWing)

    思路:
    不能修改数组,原来的方法,移动元素让下标和值相对应这个方法就用不了,又不能用额外的空间,也就是不能用打卡标记的方法了。正确的姿势是分治法,分的区间是数的范围,*如果在这个范围的数字个数大于区间长度,那么这个区间内一定有数字重复了。*继续对该区间进行划分,直到区间长度为1为止。时间复杂度:分治法为O(lgn),每次都要统计区间范围内的数字,复杂度为O(n)
    所以总的复杂度为O(nlgn)。

    1、如样例nums = [2, 3, 5, 4, 3, 2, 6, 7],分区间1-3,4-7;前面的区间范围内的数字个数为4,后面为3,很明显前面的区间内有数字重复了。
    2、继续对前面的区间划分:1-2,3;前面的区间范围内的数字个数为2,后面为2,后面的区间有数字重复了(题目只让我们返回一个重复的数字,如果有多个随便挑一个就OK了)。
    3、区间长度为1,个数却有两个,这个数字重复了,退出循环,返回该数字。

    参考代码:

    class Solution {
        public int duplicateInArray(int[] nums) 
    	{
    		int l=1,r=nums.length-1;
    		int mid=(l+r)/2;
    		while(l!=r)
    		{
    			int lNum=cnt(nums,l,mid);
    			int rNum=cnt(nums,mid+1,r);
    			if(lNum>mid-l+1)
    				r=mid;
    			else
    				l=mid+1;
    			mid=(l+r)/2;
    		}
    		return l;
        }
    
    	private int cnt(int[] nums, int l, int mid) 
    	{
    		int count=0;
    		for(int in:nums)
    			if(in>=l&&in<=mid)
    				count++;
    		return count;
    	}
    }
    
    展开全文
  • 之前有写过 找出数组中只出现一次的数,今天再来看下怎么找出数组中重复出现的数。有一个长度为 n 的数组,所有的数字都在 0~n-1 的范围,现在要求找出数组中任意一个重复的数字。这个题目看起来很简单,看看下面几...

    之前有写过 找出数组中只出现一次的数,今天再来看下怎么找出数组中重复出现的数。

    有一个长度为 n 的数组,所有的数字都在 0~n-1 的范围,现在要求找出数组中任意一个重复的数字。

    这个题目看起来很简单,看看下面几种思路。

    思路一:

    先给数组排序,然后再遍历一遍有序数组,依次比较相邻元素,就很容易能找出数组中重复的值。使用快排排序的话时间复杂度为 O(nlogn) 。

    思路二:

    利用空间换时间的思想,新建一个哈希表,然后遍历数组,每扫描一个元素都去哈希表里查找是否也存在该元素,如果存在,即找到一个重复的数,如果不存在,则将该元素保存到哈希表。这个思路的时间复杂度为 O(n),但空间复杂度也为 O(n)。

    思路三:

    认真审题,你会发现有一些特点,长度为 n 的数组,且元素的大小范围为 0~n-1,如果没有重复的数字的话,那么数组排序后数字 i 就是下标 i 所在的位置了,即 arr[i] == i。所以我们可以巧妙利用数组的下标特性来寻找解决方案。

    如果上面那句话还没看明白,看下面这个例子你就知道了。

    #arr数组中没有重复元素的情况
    #数组长度为7,元素范围为0-6
    arr = [0,1,2,3,4,5,6]
    arr[0] == 0
    arr[1] == 1
    arr[2] == 2
    

    我们通过一个具体的例子来捋一捋思路,先准备一个数组。

    arr = [4,1,1,3,5,2,5]
    

    从头开始遍历数组,判断 arr[i] 是否等于 i,如果等于则无需任何操作继续往后遍历。

    如果 arr[i] 不等于 i,则继续拿 arr[i] 和 arr[arr[i]] 比较,如果 arr[i] 和 arr[arr[i]] 相等,则找到一个重复的数,因为该数字在 i 下标和 arr[i] 下标同时出现了。

    如果 arr[i] 和 arr[arr[i]] 不相等,那就交换他们的位置,交换的目的就是为了把 arr[i] 放到属于他的位置,保证 arr[i] == i。

    交换了之后,再重复上面的比较、交换操作,直到找到一个重复的数。

    arr = [4,1,1,3,2,5,5]
    
    arr[0] != 0
    则比较 arr[0] 和 arr[4]
    
    arr[0] != arr[4]
    则交换 arr[0] 和 arr[4] 的位置
    
    新数组变成
    arr = [2,1,1,3,4,5,5]
    
    再从头开始遍历比较
    arr[0] != 0
    则比较 arr[0] 和 arr[2]
    
    arr[0] != arr[2]
    则交换 arr[0] 和 arr[2] 的位置
    
    新数组变成
    arr = [1,1,2,3,4,5,5]
    
    再从头开始遍历比较
    arr[0] != 0
    则比较 arr[0] 和 arr[1]
    
    arr[0] == arr[1]
    找到一个重复的数
    

    你可能会问,为什么要交换,交换的目的就是为了把元素放到属于它的位置上,要让这个数组满足 arr[i] == i,换句话说就是不断的调整数组,使其满足 arr[i] == i,比如数组中第一个元素 arr[0] 为 4 ,那就要把元素 4 放到下标为 4 的位置上去。下面是一份用 python 实现的完整代码,大家可以参考下。

    # encoding=utf-8
    
    def findDuplicate(arr):
        if arr is None:
            return False
    
        for i in arr:
            while arr[i] != i:
                if (arr[i] == arr[arr[i]]):#找到重复的值
                    return arr[arr[i]]
                else:#如果不相等就交换位置
                    temp = arr[arr[i]]
                    arr[arr[i]] = arr[i]
                    arr[i] = temp
        return False
    
    
    arr = [4,1,1,3,5,2,5]
    
    print(findDuplicate(arr))
    

    看完这篇文章,大家主要是知道在处理有关数组这种数据结构的问题时,要善于利用数组下标这个隐藏的条件,如果文章对你有帮助,就点个赞哈,感谢支持。

    展开全文
  • 数组中重复的

    2019-04-02 17:07:25
    之前有写过找出数组中只出现一次的数,今天再来看下怎么找出数组中重复出现的数。 有一个长度为n的数组,所有的数字都在0~n-1的范围,现在要求找出数组中任意一个重复的数字。 这个题目看起来很简单,看看...

     

    之前有写过 找出数组中只出现一次的数,今天再来看下怎么找出数组中重复出现的数。

     

    有一个长度为 n 的数组,所有的数字都在 0~n-1 的范围,现在要求找出数组中任意一个重复的数字。

     

    这个题目看起来很简单,看看下面几种思路。

     

    思路一:

     

    先给数组排序,然后再遍历一遍有序数组,依次比较相邻元素,就很容易能找出数组中重复的值。使用快排排序的话时间复杂度为 O(nlogn) 。

     

    思路二:

     

    利用空间换时间的思想,新建一个哈希表,然后遍历数组,每扫描一个元素都去哈希表里查找是否也存在该元素,如果存在,即找到一个重复的数,如果不存在,则将该元素保存到哈希表。这个思路的时间复杂度为 O(n),但空间复杂度也为 O(n)。

     

    思路三:

     

    认真审题,你会发现有一些特点,长度为 n 的数组,且元素的大小范围为 0~n-1,如果没有重复的数字的话,那么数组排序后数字 i 就是下标 i 所在的位置了,即 arr[i] == i。所以我们可以巧妙利用数组的下标特性来寻找解决方案。

     

    如果上面那句话还没看明白,看下面这个例子你就知道了。

     

    #arr数组中没有重复元素的情况
    #数组长度为7,元素范围为0-6
    arr = [0,1,2,3,4,5,6]
    arr[0] == 0
    arr[1] == 1
    arr[2] == 2
    

     

    我们通过一个具体的例子来捋一捋思路,先准备一个数组。

     

    arr = [4,1,1,3,5,2,5]
    

     

    从头开始遍历数组,判断 arr[i] 是否等于 i,如果等于则无需任何操作继续往后遍历。

     

    如果 arr[i] 不等于 i,则继续拿 arr[i] 和 arr[arr[i]] 比较,如果 arr[i] 和 arr[arr[i]] 相等,则找到一个重复的数,因为该数字在 i 下标和 arr[i] 下标同时出现了。

     

    如果 arr[i] 和 arr[arr[i]] 不相等,那就交换他们的位置,交换的目的就是为了把 arr[i] 放到属于他的位置,保证 arr[i] == i。

     

    交换了之后,再重复上面的比较、交换操作,直到找到一个重复的数。

     

    arr = [4,1,1,3,2,5,5]
    
    arr[0] != 0
    则比较 arr[0] 和 arr[4]
    
    arr[0] != arr[4]
    则交换 arr[0] 和 arr[4] 的位置
    
    新数组变成
    arr = [2,1,1,3,4,5,5]
    
    再从头开始遍历比较
    arr[0] != 0
    则比较 arr[0] 和 arr[2]
    
    arr[0] != arr[2]
    则交换 arr[0] 和 arr[2] 的位置
    
    新数组变成
    arr = [1,1,2,3,4,5,5]
    
    再从头开始遍历比较
    arr[0] != 0
    则比较 arr[0] 和 arr[1]
    
    arr[0] == arr[1]
    找到一个重复的数
    

     

    你可能会问,为什么要交换,交换的目的就是为了把元素放到属于它的位置上,要让这个数组满足 arr[i] == i,换句话说就是不断的调整数组,使其满足 arr[i] == i,比如数组中第一个元素 arr[0] 为 4 ,那就要把元素 4 放到下标为 4 的位置上去。下面是一份用 python 实现的完整代码,大家可以参考下。

     

    # encoding=utf-8
    
    def findDuplicate(arr):
        if arr is None:
            return False
    
        for i in arr:
            while arr[i] != i:
                if (arr[i] == arr[arr[i]]):#找到重复的值
                    return arr[arr[i]]
                else:#如果不相等就交换位置
                    temp = arr[arr[i]]
                    arr[arr[i]] = arr[i]
                    arr[i] = temp
        return False
    
    
    arr = [4,1,1,3,5,2,5]
    
    print(findDuplicate(arr))
    

     

    看完这篇文章,大家主要是知道在处理有关数组这种数据结构的问题时,要善于利用数组下标这个隐藏的条件,如果文章对你有帮助,就点个赞哈,感谢支持。

    展开全文
  • 索引用于快速找出在某个列中有一特定值的行,不使用索引,MySQL必须从第一条记录开始读完整个表,直到找出相关行,表越大,查询数据所花费时间就越多,如果表中查询列有一个索引,MySQL能够快速到达一个位置去...
  • 之前有写过 找出数组中只出现一次的数,今天再来看下怎么找出数组中重复出现的数。有一个长度为 n 的数组,所有的数字都在 0~n-1 的范围,现在要求找出数组中任意一个重复的数字。这个题目看起来很简单,看看下面几...
  • 前言 这几天作业,用到了k_means聚类,作为一名deeper,怎么能不手动实现一下呢?然后,我就错过了作业的提交时间。。。。 实现 原理 简单来说,可以分为以下几...将所有的情况进行计算,找出最小的(也可以通过设置阈
  • 你必须知道495个C语言问题

    千次下载 热门讨论 2015-05-08 11:09:25
    这样看来,所有的问题都解决了,是吗? 1.4 新的64位机上的64位类型是什么样的? 指针声明 1.5 这样的声明有什么问题?char*p1,p2;我在使用p2的时候报错了。 1.6 我想声明一个指针,并为它分配一些空间,但却...
  • excel使用

    2012-11-25 17:06:01
    ”则隐藏所有的输入。 自定义格式只改变数据的显示外观,并不改变数据的,也就是说不影响数据的计算。灵活运用好自定义格式功能,将会给实际工作带来很大的方便。5、绘制函数图象做教学工作的朋友们一定会遇到画...
  • 最近出去面试发现面试官特别喜欢提问海量数据处理问题,本场 Chat 就搜集一些互联网公司喜欢问海量数据...怎么在海量数据中找出重复次数最多一个? 当前内容版权归码字科技所有并授权显示,盗版必究。阅读原文
  • 这样看来,所有的问题都解决了,是吗? 2  1.4 新的64位机上的64位类型是什么样的? 3 指针声明 3 1.5 这样的声明有什么问题?char *p1, p2; 我在使用p2的时候报错了。 3 1.6 我想声明一个指针,并为它分配...
  • 《你必须知道495个C语言问题》

    热门讨论 2010-03-20 16:41:18
    这样看来,所有的问题都解决了,是吗? 2  1.4 新的64位机上的64位类型是什么样的? 3 指针声明 3 1.5 这样的声明有什么问题?char *p1, p2; 我在使用p2的时候报错了。 3 1.6 我想声明一个指针,并为它分配...
  • 怎么找出L组合呢?饭店是每隔K 有一个,是重复的,我们只需要算出第一个饭店两侧,起点和停顿点情况,之后再加上k1 ,k2,k*3 就能得出所有L组合。 数据范围是 10万,所以必须要用long long int。 还有就是对于...
  • 腾讯后台开发面经

    2021-03-11 16:49:38
    如果有一个几个G文件,存储了uint32数据,在内存不够大不能一次性读入所有数据情况下,怎么找出中位数。 3.算法题 给一个只有小写字母字符串,找出不重复的字母中,第一个出现位置。 4.C++传参方式有哪些...
  • 1.6.1 使用DISTINCT消除重复值 18 1.6.2 在聚合函数中使用DISTINCT 18 1.6.3 使用列别名 19 1.6.4 使用SELECT创建脚本 20 1.6.5 字符串拼接 21 1.6.6 使用SELECT创建逗号分隔列表 21 1.6.7 使用INTO...
  • flashmtv制作

    2011-11-17 18:15:11
    利用任意一种软件,把所有的歌词编辑好,并按歌词顺序作好标记,歌词制作好以后以swf格式保存在电脑硬盘中,需要的时候直接导入到Flash中。 歌词的导入:打开歌词层小锁,点菜单栏上【插入】-【新建元件】命令,...
  • 3.4.8 找出数组中出现次数超过一半数,现在有一个数组,已知一个数出现次数超过了一半,请用O(n)复杂度算法找出这个数。 3.4.9 找出被修改过数字 3.5.0 设计DNS服务器中cache数据结构。要求设计一个...
  • 第五步:重复第四步,计算出所有网页每个词tf-idf 。3、处理用户查询第一步:对用户查询进行分词。第二步:根据网页库(文档)数据,计算用户查询中每个词tf-idf 。4、相似度计算使用余弦相似度来计算...
  • 恨不得把所有的知识统统都塞到肚子里去。看到什么,想学什么!这是几 乎所有在校大学生的通病。但是,这不是坏事,甚至可以说是好事。说明了你“求知欲”高! 总比那些,生活没有激情,整天知道泡妞、上网、打游戏...
  • 但是有时却无法找出LLC帧首部各字段的值。这是什么原因? 问题4-22:整个IEEE 802委员会现在一共有多少个工作组? 问题4-23:在一些文献和教材中,可以见到关于以太网“前同步码”(preamble)有两种不同说法...
  • 1.7.4 找出其他用户所属于组 10 1.8 umask 10 1.8.1 如何计算umask 10 1.8.2 常用umask 11 1.9 符号链接 12 1.9.1 使用软链接来保存文件多个映像 12 1.9.2 符号链接举例 12 1.10 小结 13 第2章 使用find和...
  • 1.7.4 找出其他用户所属于组 10 1.8 umask 10 1.8.1 如何计算umask 10 1.8.2 常用umask 11 1.9 符号链接 12 1.9.1 使用软链接来保存文件多个映像 12 1.9.2 符号链接举例 12 1.10 小结 13 第2章 使用find和...
  • 然后绘制出所有的金币对象 如果要运动起来,每一帧让每个金币的y轴位置往下掉一点,就是这句y: coin.y + coin.speed,那么绘制下一帧时,其他信息都不变,每个金币都往下移动了一...

空空如也

空空如也

1 2 3 4 5 ... 7
收藏数 121
精华内容 48
关键字:

怎么找出所有的重复值