python数组中的 k-diff 数对例题解析

目录
  • 一、题目描述
  • 二、思路分析
    • 方法一：构建哈希表
    • 方法二：双指针
  • 三、总结

一、题目描述

题目内容：

题目示例：

题目解析：

  • 1 <= nums.length <= 104
  • -107 <= nums[i] <= 107
  • 0 <= k <= 107

二、思路分析

我们拿到本题，读取题意要求在一组整数数组中，求出差值为k的数对对数k-diff。在思考如何解答该题之前，需要明确如下几点细节：

  • nums数组元素都是整数
  • 索引位置i与位置j,不能相等
  • k-diff数对关系：nums[i] - nums[j] = k -> nums[i] = nums[j] + k -〉 nums[i] - k = nums[j]
  • k-diff数对，存在相同数对情况，但结果只取1次

因此，我们的对题目中进行详细了解了，因为会排除重复的数对，我们很容易想哈希表来构建

方法一：构建哈希表

根据上述思路，我们使用python代码能快速实现，代码如下：

class Solution(object):
    def findPairs(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        ans = set()
        numset = set()
        for num in nums:
            if num - k in numset:
                ans.add(num-k)
            if num + k in numset:
                ans.add(num)
            numset.add(num)
        return len(ans)
  • 数对中重复场景如示例一中差值为k=1,(1,3) & (3,1)视为一种情况，则要定义两个哈希表来储存
  • 哈希表可以通过字典k-value或者集合set(),本题无需考虑索引关系定义ans,numset两个集合
  • 当 nums[i] > nums[j],则nums[j] = nums[i] - k在numset中，取最小的那一个则ans.add(nums[i]-k),
  • 当 nuns[i] < nums[j],则nums[j] = nums[i] + k 在numset中，取较小的那一个则ans.add(nums[i])

方法二：双指针

根据上述思路，使用python代码实现，代码如下：

class Solution(object):
    def findPairs(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        nums.sort()
        ans = 0
        j = 0
        for i in range(len(nums)):
            if i == 0 or nums[i] != nums[i-1]:
                while j < len(nums) and (nums[j] < nums[i] + k or j <= i):
                    j +=1
                if j < len(nums) and nums[j] == nums[i] + k:
                    ans +=1
        return ans
  • 首先对nums数组中的元素按照从低到高的顺序排列
  • 在递增的数组中，由于双指针 i!=j，因此i指针一定是小于j的
  • 枚举查找的判断的条件 nums[j] < nums[i]+k,指针j则往后移动
  • 当nums[j] = nums[i] + k 时，则对数次数+1

三、总结

本题可以使用哈希方法要使用两个哈希表，属于牺牲空间换取效率。双指针方法，虽然没有用额外的空间，但是速度较于方法一慢一点。

我们用第一种方法，AC提交记录如下：

  • 时间复杂度O(n),n为nums长度
  • 空间复杂度O(n),需要使用哈希表，n为nums长度

到此这篇关于python数组中的 k-diff 数对例题解析的文章就介绍到这了,更多相关python k-diff 内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • 用python标准库difflib比较两份文件的异同详解

    [需求背景] 有时候我们要对比两份配置文件是不是一样,或者比较两个文本是否异样,可以使用linux命令行工具diff a_file b_file,但是输出的结果读起来不是很友好.这时候使用python的标准库difflib就能满足我们的需求. 下面这个脚本使用了difflib和argparse,argparse用于解析我们给此脚本传入的两个参数(即两份待比较的文件),由difflib执行比较,比较的结果放到了一个html里面,只要找个浏览器打开此html文件,就能直观地看到比较结果,两份文件有差

  • python difflib模块示例讲解

    python difflib模块示例讲解

    difflib模块提供的类和方法用来进行序列的差异化比较,它能够比对文件并生成差异结果文本或者html格式的差异化比较页面,如果需要比较目录的不同,可以使用filecmp模块. class difflib.SequenceMatcher 此类提供了比较任意可哈希类型序列对方法.此方法将寻找没有包含'垃圾'元素的最大连续匹配序列. 通过对算法的复杂度比较,它由于原始的完形匹配算法,在最坏情况下有n的平方次运算,在最好情况下,具有线性的效率. 它具有自动垃圾启发式,可以将重复超过片段1%或者重复20

  • python numpy中setdiff1d的用法说明

    python numpy中setdiff1d的用法说明

    一.函数解释 setdiff1d(ar1, ar2, assume_unique=False) 1.功能:找到2个数组中集合元素的差异. 2.返回值:在ar1中但不在ar2中的已排序的唯一值. 3.参数: ar1:array_like 输入数组. ar2:array_like 输入比较数组. assume_unique:bool.如果为True,则假定输入数组是唯一的,即可以加快计算速度. 默认值为False. 二.具体示例 1.assume_unique = False的情况: a = np.

  • Python 比较文本相似性的方法(difflib,Levenshtein)

    最近工作需要用到序列匹配,检测相似性,不过有点复杂的是输入长度是不固定的,举例为: input_and_output = [1, 2, '你好', 世界', 12.34, 45.6, -21, '中国', '美丽'] 其中,需要从input_and_output 中选取不固定长度的一段作为输入,且顺序不定,然后去与总体进行比较,找出最符合的,开始是对汉字进行数值化编码,不过后来由于出现汉字越来越多,遂放弃该方法,转向别的方式,查找资料发现了两个python包广被推荐,从下面来看各有优缺点,记录之

  • python数组中的 k-diff 数对例题解析

    python数组中的 k-diff 数对例题解析

    目录 一.题目描述 二.思路分析 方法一:构建哈希表 方法二:双指针 三.总结 一.题目描述 题目内容: 题目示例: 题目解析: 1 <= nums.length <= 104 -107 <= nums[i] <= 107 0 <= k <= 107 二.思路分析 我们拿到本题,读取题意要求在一组整数数组中,求出差值为k的数对对数k-diff.在思考如何解答该题之前,需要明确如下几点细节: nums数组元素都是整数 索引位置i与位置j,不能相等 k-diff数对关系:n

  • 深入线性时间复杂度求数组中第K大数的方法详解

    求数组中第K大的数可以基于快排序思想,步骤如下:1.随机选择一个支点2.将比支点大的数,放到数组左边:将比支点小的数放到数组右边:将支点放到中间(属于左部分)3.设左部分的长度为L,当K < L时,递归地在左部分找第K大的数当K > L时,递归地在有部分中找第(K - L)大的数当K = L时,返回左右两部分的分割点(即原来的支点),就是要求的第K大的数以上思想的代码实现如下: 复制代码 代码如下: /**线性时间复杂度求数组中第K大数** author :liuzhiwei ** data 

  • PHP实现找出有序数组中绝对值最小的数算法分析

    本文实例讲述了PHP实现找出有序数组中绝对值最小的数算法.分享给大家供大家参考,具体如下: 问题: 一个有序数组,值有可能有负值,也有可能没有,现需要找出其中绝对值最小的值. 方法1: 遍历数组,找到绝对值最小值,时间复杂度O(n),n为元素个数. 方法2: 二分查找,因为数组有序,可以利用二分查找,时间复杂度O(logn). 分析步骤: 1. 如果第一个数为正数,说明整个数组没有负数,直接返回第一个数 2. 如果最后一个数为负数,说明整个数组没有正数,直接返回最后一个数 3. 数组元素有正有负

  • 详解python数组中的符号...与:符号的不同之处

    不知道大家有没有见过在python数组中使用...符号,因为前段时间读别人代码的时候遇到了这个符号立刻就云里雾里,于是这里特此记录一下.先来看一段代码: import numpy as np x = np.array([[1, 3], [5, 6], [8, 10]]) print("使用'...'符号的结果为:") print(x[..., 0]) print("使用':'符号的结果为:") print(x[:, 0]) """ 使用

  • C#递归算法寻找数组中第K大的数

    1.概述 国人向来喜欢论资排辈的,每个人都想当老大,实在当不成,当个老二,老三,老K也不错,您一定看过这样的争论: 两个人吵架,一个人非常强势,另外一个忍受不住了便说:"你算老几呀?",下面就通过这篇文章就是要解决找出老几的问题! 2.应用场景 在向量V[first,last)中查找出第K大元素的值 3.分析 如果利用排序算法将向量V排好序,那么第K大元素就是索引为v.length-k的元素了,这样能解决问题,但效率不高,因为这相当于为了歼灭敌人一个小队而动用了我们全军的力量,得不偿失

  • Python编程中time模块的一些关键用法解析

    Python编程中time模块的一些关键用法解析

    python中time模块其实不难,就是关系转换有点老记不住,先看下图可以说明几个时间对象的的关系.供参考理解. 黑色细箭头表示输入值,参数 深黄色的粗箭头表示返回值,输出格式 绿色圆圈表示各类对象 蓝色方框表示具体的方法 (先import time,在使用time模块中的方法) time.time():获取当前时间的时间戳 time.localtime():接受一个时间戳,并把它转化为一个当前时间的元组.不给参数的话就会默认将time.time()作为参数传入,localtime返回tuple

  • Python类中的魔法方法之 __slots__原理解析

    在类中每次实例化一个对象都会生产一个字典来保存一个对象的所有的实例属性,这样非常的有用处,可以使我们任意的去设置新的属性. 每次实例化一个对象python都会分配一个固定大小内存的字典来保存属性,如果对象很多的情况下会浪费内存空间. 可通过__slots__方法告诉python不要使用字典,而且只给一个固定集合的属性分配空间 class Foo(object): __slots__ = ("x","y","z") def __init__(sel

  • C++算法之在无序数组中选择第k小个数的实现方法

    本文实例讲述了C++算法之在无序数组中选择第k小个数的实现方法.分享给大家供大家参考,具体如下: 从一个无序的整型数组中选出第k小的数,如k=1为最小数,k=n为最大数.这里数组可以是有重复的值! 下面是自己写的一个函数,记在此处来记忆我留下的痕迹! //选择无序数组中第k小的数 #include <iostream> using namespace std ; bool failed = false ; //这里只考虑数组是int型的 int findnumber(int *array,in

  • python爬虫中抓取指数的实例讲解

    python爬虫中抓取指数的实例讲解

    有一些数据我们是没法直观的查看的,需要通过抓取去获得.听到指数这个词,有的小伙伴们觉得很复杂,似乎只在股票的时候才听说的,比如一些数据的涨跌分析都是比较棘手的问题.不过指数对于我们的数据分析还是很有帮助的,今天小编就python爬虫中抓取指数得方法给大家带来讲解. 刚好这几天需要用到这个爬虫,结果发现baidu指数的请求有点变化,所以就改了改: import requests import sys import time word_url = 'http://index.baidu.com/ap

  • JS中取二维数组中最大值的方法汇总

    在JavaScript中可以通过内置的 Math.max() 的最大值,但是要从多重数组中取出最大值,还是有一定的难度. 问题描述 假设你有一个数组,而且这个数组中包含了数字的子数组,而我们要做的是从数组中的每个子数组中返回其最大的那个最大数. 基本解决方案 function largestOfFour(arr) { var results = []; // 创建一个results变量来存储 // 创建一个外层循环,遍历外层数组 for (var n = 0; n < arr.length; n

随机推荐