首页 > 其他分享 >Contains Duplicate II

Contains Duplicate II

时间:2022-12-13 16:07:12浏览次数:58  
标签:numsSize index 数组 nums int Contains II Duplicate key


​https://leetcode.com/problems/contains-duplicate-ii/​

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

这道题目源自 [Contains Duplicate] (​​javascript:void(0)​​)

不同的是查找到的两个相同元素的下标距离不能超过给定的参数K。所以可以把上个题目改进一下,创建一个index数组,将nums数组元素排序前后的index关系映射存储起来,比如有个元素3的原先的下标是 i,排序过后的下表到了数组的位置j, 则有 index[j]=i;

bool containsNearbyDuplicate(int* nums, int numsSize, int k) {
int i, j, key;
int *index = (int *)malloc(numsSize * sizeof(int)); // store index
//memset(index, 0, numsSize * sizeof(int));

for(i = 1; i < numsSize; ++i) {
j = i - 1;
key = nums[i];
while(j > 0 && nums[j] > key) {
nums[j + 1] = nums[j]; // move to back
index[j + 1] = index[j];
j--;
}

//if(j != (i-1))
//{
nums[j + 1] = key;
index[j + 1] = i; // map new index to old
//}

/* check */
if((nums[j] == key) && (i - index[j] <= k))
return true;
}

free(index);

return false;
}


标签:numsSize,index,数组,nums,int,Contains,II,Duplicate,key
From: https://blog.51cto.com/u_15911341/5934354

相关文章

  • Contains Duplicate
    ​​https://leetcode.com/problems/contains-duplicate/​​Givenanarrayofintegers,findifthearraycontainsanyduplicates.Yourfunctionshouldreturntrue......
  • The Complete Guide to C++ Strings, Part II - String Wrapper Classes
    TheCompleteGuidetoC++Strings,PartII-StringWrapperClasses IntroductionSinceC-stylestringscanbeerror-proneanddifficulttomanage,......
  • STM32H747IIT6(2MB)STM32H747IGT6(1MB)STM32H747BIT6高性能MCU资料
    概述:STM32H7高性能MCU基于高性能ArmCortex-M732位RISC内核,工作频率高达400MHz。Cortex-M7内核具有浮点单元(FPU)精度,支持Arm双精度(符合IEEE754标准)和单精度数据处理指......
  • IIS 运行PHP 正常使用MYSQL 解决报错0x000000ff
    extension=php_mysql.dllextension=php_mysqli.dlldate.timezone=Asia/Shanghai注意:php.ini 下:extension_dir="D:\SoftWare\DEVPHP\php_5_3_13\ext"否则会报错......
  • 环形链表II
    题目地址(142.环形链表II)​​https://leetcode-cn.com/problems/linked-list-cycle-ii/​​题目描述给定一个链表,返回链表开始入环的第一个节点。如果链表无环,则返回nu......
  • 19.13备库duplicate恢复新主库(二)
    问题描述:主备两个库不在同一个机房,此时想从这一套库中在复制一套可读可写的新库出来。网络带宽要求比较高,需要从备库中使用备份在起一个新库,也要测试下使用duplicate从备库......
  • 剑指Offer II 001.整数除法
    题目描述整数除法:给定两个整数a和b,求它们的除法的商a/b,要求不得使用乘号'*'、除号'/'以及求余符号'%' 。注意:整数除法的结果应当截去(truncate)其小数部分,例......
  • 脑筋急转弯-2498. 青蛙过河 II
    2498.青蛙过河IIDescriptionDifficulty:中等RelatedTopics:给你一个下标从0 开始的整数数组 stones ,数组中的元素 严格递增 ,表示一条河中石头的位置。一只......
  • BZOJ4536 : 最大异或和II
    建立$n+m$个点的无向图,其中$n$个点表示输入的数列,$m$个点表示答案的$m$个二进制位。对于输入的两个数$a[i],a[j]$,若它们存在公共二进制位,则可以通过同时选某一公共位来对......
  • python-miio 入门
    一、获取ip和tooken转载链接:https://github.com/PiotrMachowski/Xiaomi-cloud-tokens-extractor二、基础通信转载链接:https://github.com/rytilahti/python-miio/iss......