Python面试不修改数组找出重复的数字

目录
  • 数组中重复的数字
  • 不修改数组找出重复的数字
  • 思路
    • 思路一：哈希表
    • 思路二：二分法
  • 测试
  • 总结

数组中重复的数字

在上一篇博客中剑指Offer之面试题3: 数组中重复的数字中，其实能发现这类题目的关键就是一边遍历数组一边查满足条件的元素。

然后我们在博客​用最复杂的方式学会数组（Python实现动态数组）​这篇博客中介绍了数组这一结构的本质，并自己动手实现了一个动态数组。

今天我们介绍一下另一道来自《剑指Offer》的关于数组的面试题——不修改数组找出重复的数字。

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

题目二：不修改数组找出重复的数字

给定一个长度为 n+1 的数组里的所有数字都在 0∼n 的范围内，所以数组中至少有一个数字是重复的。

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

样例：

给定长度为8的数组 nums = [2， 3， 5， 4，3， 2， 6，7]

那么输出重复的数字2或者3

思路

首先我们得关注到，题目要求是：不修改数组，然后还是 ​​ 返回任意一个重复的数字​​ 。所以解题思路相比而言变少了：

1.哈希表：跟上一题一样，本题也可以创建一个哈希表，如果原数组的每个数字第一次出现，就把他放到哈希表中去，即原数组大小为m的数字应该放到哈希表下标为m的位置上。空间复杂度是 $O(n)$ 。

2.二分法：那么有没有不用空间复杂度 $O(n)$ 的算法。假设没有重复数，那么​​1~n​​ 之间，每个数都只能出现一次。而题目中，这个数组至少有一个数字重复，即出现的次数大于1。

利用二分的思想：把 ​​1~n​​ 的数字从中间数字 m 开始分为两部分，前一半为 1~ m，后面一半为 ​​m+1 ~n​​​，如果 ​​1~m​​ 中的数字在数组中出现的次数大于 m，那么这一半必定有重复的数字；

否则，那么另一部分必定含有重复数字。接着我们，继续对含有重复数字的区间一分为二，直到找到重复的数字。

思路一：哈希表

def find_duplicated_num(nums):
    """hash_map"""
    hash_map = dict()
    for i, val in enumerate(nums):
        if val in hash_map:
            return val
        hash_map[val] = i
    return False

思路二：二分法

def reduce_inter(nums2, left, right):
    """ """
    mid = (left + right) // 2
    count = 0
    length = len(nums2)
    for i in range(length):
        if (nums2[i] >= left) and (nums2[i] <= mid):
            count += 1
    if count > mid - left + 1:
        return left, mid
    else:
        return mid+1, right

def find_duplicated_num2(nums2):
    left, right = 1, len(nums2) - 1
    while left != right:
        left, right = reduce_inter(nums2, left, right)
    return left

测试

nums = [2, 3, 5, 4, 3, 2, 6, 7]
# nums_n = [5, 4, 3, 2, 6, 7]
print("思路一测试结果: ", find_duplicated_num(nums))
print("思路二测试结果: ", find_duplicated_num2(nums))

结果

思路一测试结果:  3
思路二测试结果:  3

总结

其实，这种算法不能保证找出所有重复的数字，比如不能找出[2, 3, 5, 4, 3, 2, 6, 7]重复数字2。

以上就是不修改数组找出重复的数字Python实现的详细内容，更多关于python找出重复数字的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • python 实现二维数组的索引、删除、拼接操作

    python 实现二维数组的索引、删除、拼接操作

    1.数组的索引 我用的是iloc函数.导入数据是data,索引data.iloc[i,j],i代表行,j代表列.如果要索引i行之后的所有行元素,使用data.iloc[i:,j], i行之前的所有行,使用data.iloc[:i,j]. 2.数组的拼接 可以使用append函数.np.apend(a,b),a和b为待拼接的数组. 由于我需要把一维数组按行拼接成二维数组,选择vstack函数,可以实现垂直方向的拼接.np.vstack((a,b)) 3.数组删除一行或多行元素 我用的是drop函数

  • python计算数字或者数组的阶乘的实现

    今天写毕业设计的时候遇到了一个级数展开式,里面包含着一个求一个数组的阶乘运算,这里特来记录一下. # -*- coding:utf-8 -*- """ author: 15025 time: 2021/7/18 17:58 software: PyCharm Description: calculate factorial of a given number """ class PythonStudy: @staticmethod def fac

  • Python多进程共享numpy 数组的方法

    Python多进程共享numpy 数组的方法

    为什么要用numpy Python中提供了list容器,可以当作数组使用.但列表中的元素可以是任何对象,因此列表中保存的是对象的指针,这样一来,为了保存一个简单的列表[1,2,3].就需要三个指针和三个整数对象.对于数值运算来说,这种结构显然不够高效.     Python虽然也提供了array模块,但其只支持一维数组,不支持多维数组(在TensorFlow里面偏向于矩阵理解),也没有各种运算函数.因而不适合数值运算.     NumPy的出现弥补了这些不足. 引用:https://zhuanl

  • python数组排序方法之sort、sorted和argsort详解

    目录 引言 sort和sorted的区别如下 用法实例 1.升序排序 2.降序排序 3.如果不想要排序后的值,想要排序后的索引,可以这样做 4.字符串类型排序 5.二维数组排序 6.二维数组获取排序后的索引 7.字典数组排序 8.字典数组获取排序后的索引 9.对象排序 10.对象排序获取排序后的索引 11.一维数组排序[numpy] 12.一维数组获取排序后的索引[numpy] 13.一维数组降序排序[numpy] 14.二维数组排序[numpy] 15.二维数组获取排序后的索引[numpy]

  • Python中numpy数组的计算与转置详解

    Python中numpy数组的计算与转置详解

    目录 前言 1.numpy数组与数的运算 2.numpy相同尺寸的数组运算 3.numpy不同尺寸的数组计算 4.numpy数组的转置 总结: 前言 本文主要讲述numpy数组的计算与转置,讲相同尺寸数组的运算与不同尺寸数组的运算,同时介绍数组转置的三种方法. numpy数组的操作比较枯燥,但是都很实用,在很多机器学习.深度学习算法中都会使用到,对numpy数组的一些操作. 1.numpy数组与数的运算 主要包括数组与数的加减乘除运算,废话不多说,看代码: import numpy as np

  • Python面试不修改数组找出重复的数字

    目录 数组中重复的数字 不修改数组找出重复的数字 思路 思路一:哈希表 思路二:二分法 测试 总结 数组中重复的数字 在上一篇博客中剑指Offer之面试题3: 数组中重复的数字中,其实能发现这类题目的关键就是一边遍历数组一边查满足条件的元素. 然后我们在博客​用最复杂的方式学会数组(Python实现动态数组)​这篇博客中介绍了数组这一结构的本质,并自己动手实现了一个动态数组. 今天我们介绍一下另一道来自<剑指Offer>的关于数组的面试题——不修改数组找出重复的数字. 不修改数组找出重复的数字

  • 剑指offer之C语言不修改数组找出重复的数字

    1  题目 不修改数组找出重复的数字 在一个长度为N+1的数组里面的所有数字都在范围1~N范围内,所以数组至少有一个数字是重复的,请找出重复数字,但是不能修改输入的数组. 2  思路 思路1: 我们开辟一个新的数组,初始化为0,然后把原始数组每个数据的值作为下标,把新数组通过这个下标数据取出来,如果取出来是1,就说明这个下标数据重复了,如果不是,我们直接放进去,然后进行新数组值进行++操作. 思路2: 比如数据1 2 2 3 4 5 6 7, 我们先找到中间的值(1 + 7) / 2 = 4;然

  • Go语言LeetCode题解961在长度2N的数组中找出重复N次元素

    目录 题目描述 思路分析 AC 代码 题目描述 961. 在长度 2N 的数组中找出重复 N 次的元素 给你一个整数数组 nums ,该数组具有以下属性: nums.length == 2 * n. nums 包含 n + 1 个 不同的 元素 nums 中恰有一个元素重复 n 次 找出并返回重复了 n 次的那个元素. 示例 1: 输入:nums = [1,2,3,3] 输出:3 示例 2: 输入:nums = [2,1,2,5,3,2] 输出:2 示例 3: 输入:nums = [5,1,5,

  • JS实现为排序好的字符串找出重复行的方法

    本文实例讲述了JS实现为排序好的字符串找出重复行的方法.分享给大家供大家参考,具体如下: 实现这样一个需求,在一个Editplus文档中,有很多行10位的数字,这些数字已经排好序了. 比如: 1234567890 1234567891 1234567892 1234534124 1234614124 4321412414 5636373573 有什么办法能方便的找出两行至少前7位相同的数字吗? 比如,上面的数字中,能够找出 1234567890 1234567891 1234567892 <!D

  • Python一句代码实现找出所有水仙花数的方法

    水仙花数是指一个 3位正整数,它的每个位上的数字的 3 次幂之和等于它本身.(例如:1^3 + 5^3+ 3^3 = 153) 下面用一句代码实现找出所有的水仙花数: 方法一: >>> >>> a = list(map(lambda x: x[1], filter(lambda x: x[0], [(i*100+j*10+k == i**3+j**3+k**3, i**3+j**3+k**3) for i in range(1, 10) for j in range(0

  • Python cookbook(数据结构与算法)找出序列中出现次数最多的元素算法示例

    本文实例讲述了Python找出序列中出现次数最多的元素.分享给大家供大家参考,具体如下: 问题:找出一个元素序列中出现次数最多的元素是什么 解决方案:collections模块中的Counter类正是为此类问题所设计的.它的一个非常方便的most_common()方法直接告诉你答案. # Determine the most common words in a list words = [ 'look', 'into', 'my', 'eyes', 'look', 'into', 'my', '

  • python列表推导式实现找出列表中长度大于5的名字

    目录 列表推导式找出列表中长度大于5的名字 任务 我的笨办法 python列表推导式 例如 列表推导式找出列表中长度大于5的名字 任务 给定一个列表,使用列表推导式找出列表中长度大于5的名字,并打印该列表 names = [[‘Tom’, ‘Billy’, ‘Jefferson’, ‘Andrew’, ‘Wesley’, ‘Steven’, ‘Joe’],[‘Alice’, ‘Jill’, ‘Ana’, ‘Wendy’, ‘Jennifer’, ‘Sherry’, ‘Eva’]] 我的笨办法 刚

  • python实现从字符串中找出字符1的位置以及个数的方法

    本文实例主要实现给出任意字符串,获取字符串中某字符的位置以及出现的总次数. 实现该功能代码的时候可以使用函数enumerate来将字符串分离成位置和字符,然后进行比较即可. 具体实现代码如下: #!/bin/env python #-*- coding:utf-8 -*- # """ 用enumerate将string中的1都找出来, 用enumerate实现: """ def get_1_pos(string): onePos=[] try:

  • Python pandas找出、删除重复的数据实例

    目录 前言 一.duplicated() 二.drop_duplicates() 总结 前言 当我们使用pandas处理数据的时候,经常会遇到数据重复的问题,如何找出重复数据进而分析重复原因,或者如何直接删除重复的数据是一个关键的步骤,pandas提供了很方便的方法:duplicated()和drop_duplicates(). 一.duplicated() duplicated()可以被用在DataFrame的三种情况下,分别是pandas.DataFrame.duplicated.panda

  • python中找出numpy array数组的最值及其索引方法

    在list列表中,max(list)可以得到list的最大值,list.index(max(list))可以得到最大值对应的索引 但在numpy中的array没有index方法,取而代之的是where,其又是list没有的 首先我们可以得到array在全局和每行每列的最大值(最小值同理) >>> a = np.arange(9).reshape((3,3)) >>> a array([[0, 1, 2], [9, 4, 5], [6, 7, 8]]) >>&

随机推荐