- 浏览: 172681 次
- 性别:
- 来自: 济南
文章分类
最新评论
给定一个数组,判断是否存在重复元素,或者让你找出重复的元素。遇到这类问题我们应该先想用哈希表,位运算,双指针是否可以解决,根据具体的情况选择合适的方法。下面是leetcode中有关数组去重或查重的几道题目。
1,Contains Duplicate
给定一个数组,判断里面是否存在重复元素,如果存在就返回true,如果不存在就返回false.
既然是判断是否存在重复元素,我们首先想到哈希表,遍历数组,存在重复元素直接return true;不重复的元素依次加入表中,直到结束。代码如下:
2,Contains Duplicate II
给定一个数组nums[],找出两个相同的元素nums[i] = nums[j], 并且满足(i > j )&& (i - j <= k)
和上一题目相比,我们只需要再找到相同元素时加一个判断就可以,当i-j <=k 时return true;
代码如下:
3,Remove Duplicates from Sorted Array
给定一个数组,删除重复的元素(in-place),使每个元素最多出现一次,然后返回新的长度。
例如给定数组nums[] = {1,1,2} 返回 2
删除元素,我们往往用两个指针来处理,一个指针用来遍历,一个用来保存处理过的元素。对于这道题,我们用一个指针遍历,当遇到相同的就继续遍历,如果不相同的,我们就把它保存。
代码如下:
4,Remove Duplicates from Sorted Array II
给定一个数组,删除重复的元素(in-place),使每个元素最多出现两次,然后返回新的长度。
与上一道题不同,它允许每个元素出现两次,基本方法我们还是采用两个指针,但我们要维护一个计数变量,来记录重复元素出现的次数,代码如下:
5,Find the Duplicate Number
给定一个数组,长度为n+1,每个元素的值在1...n之间,假设只有一个重复的值,但是这个值可能重复多次,找出这个重复的值。要求空间复杂度为O(1),时间复杂度小于O(n^2)
因为我们知道数组中元素的值,它们在1...n之间,因此我们可以通过标记,来找到重复的元素,例如数组nums = {1,1,2}; 我们从第一个元素开始处理,我们让nums[nums[0]] 的值取负数,这样num[1] 就变为了-1,如果不重复时,我们就访问不到负数,只有重复的元素,我们才能访问到负数。代码如下:
1,Contains Duplicate
给定一个数组,判断里面是否存在重复元素,如果存在就返回true,如果不存在就返回false.
既然是判断是否存在重复元素,我们首先想到哈希表,遍历数组,存在重复元素直接return true;不重复的元素依次加入表中,直到结束。代码如下:
public class Solution { public boolean containsDuplicate(int[] nums) { HashMap<Integer, Integer> hm = new HashMap<Integer,Integer>(); for(int i = 0; i < nums.length; i++) { if(hm.containsKey(nums[i])){ return true; } else { hm.put(nums[i], i); } } return false; } }
2,Contains Duplicate II
给定一个数组nums[],找出两个相同的元素nums[i] = nums[j], 并且满足(i > j )&& (i - j <= k)
和上一题目相比,我们只需要再找到相同元素时加一个判断就可以,当i-j <=k 时return true;
代码如下:
public class Solution { public boolean containsNearbyDuplicate(int[] nums, int k) { HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>(); for(int i = 0; i < nums.length; i++) { if(hm.containsKey(nums[i]) && i - hm.get(nums[i]) <= k) { return true; } else { hm.put(nums[i], i); } } return false; } }
3,Remove Duplicates from Sorted Array
给定一个数组,删除重复的元素(in-place),使每个元素最多出现一次,然后返回新的长度。
例如给定数组nums[] = {1,1,2} 返回 2
删除元素,我们往往用两个指针来处理,一个指针用来遍历,一个用来保存处理过的元素。对于这道题,我们用一个指针遍历,当遇到相同的就继续遍历,如果不相同的,我们就把它保存。
代码如下:
public class Solution { public int removeDuplicates(int[] nums) { int index = 1; for(int i = 1; i < nums.length; i++) { if(nums[i] != nums[i - 1]) nums[index++] = nums[i]; } return index; } }
4,Remove Duplicates from Sorted Array II
给定一个数组,删除重复的元素(in-place),使每个元素最多出现两次,然后返回新的长度。
与上一道题不同,它允许每个元素出现两次,基本方法我们还是采用两个指针,但我们要维护一个计数变量,来记录重复元素出现的次数,代码如下:
public class Solution { public int removeDuplicates(int[] nums) { int index = 0; int count = 0; for(int i = 0; i < nums.length; i++) { if(i > 0 && nums[i] == nums[i-1]) { if(count >= 2) { continue; } else { nums[index++] = nums[i]; count ++; } } else { nums[index++] = nums[i]; count = 1; } } return index; } }
5,Find the Duplicate Number
给定一个数组,长度为n+1,每个元素的值在1...n之间,假设只有一个重复的值,但是这个值可能重复多次,找出这个重复的值。要求空间复杂度为O(1),时间复杂度小于O(n^2)
因为我们知道数组中元素的值,它们在1...n之间,因此我们可以通过标记,来找到重复的元素,例如数组nums = {1,1,2}; 我们从第一个元素开始处理,我们让nums[nums[0]] 的值取负数,这样num[1] 就变为了-1,如果不重复时,我们就访问不到负数,只有重复的元素,我们才能访问到负数。代码如下:
public class Solution { public int findDuplicate(int[] nums) { int result = 0; for(int i = 0; i < nums.length; i++) { if(nums[Math.abs(nums[i])] > 0) { nums[Math.abs(nums[i])] = -nums[Math.abs(nums[i])]; } else { result = Math.abs(nums[i]); } } return result; } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 223Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 221You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 338Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 329Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 447Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 508Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 426Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 617Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 424The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 382Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 513Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 526Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 366All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 858Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 877Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 550Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 595Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 760Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 728You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 625For a undirected graph with tre ...
相关推荐
大致介绍 JavaScript的数组去重问题在许多面试中都会遇到,现在做个总结 先来建立一个数组 ...Array.prototype.removeDuplicate = function(){ var n = []; for(var i=0;i<this.length;i++){ if(n.indexOf
这是一款文件去重工具,支持多种条件的文件查询,以及多种方式的去除重复
文件去重Duplicate Cleaner Pro v3.24专业破解版 Duplicate Cleaner 是一款可以帮助你在你的计算机上找到并且清除副本文件的简单易用的软件。你可以立即搜索多个文件夹结构并且设置识别副本文件的标准。你可以选择...
LeetCode Remove Duplicates from Sorted Array解决方案
from IPython import embed # xy 输入,可支持浮点数操作 速度很快哦 # return xy 去重后结果 def duplicate_removal(xy): if xy.shape[0] < 2: return xy _tmp = (xy*4000).astype('i4') # 转换成 i4 处理 _...
删除重复 去重复url 删除重复网址 remove duplicate url 一个国外的删除重复网址软件
Oracle 11gR2 使用 RMAN duplicate from active database 复制数据库
对象数组去重:过滤对象数组中指定键名的重复值,不会比较其他键值,不会合并。installnpm i dedup-arrayUsagelet filteredArr = dedup(array,["key1","key2"])Demolet dedup = require("dedup-array");let array =...
重复数组 复制数组的模块
电脑文件多,不知道那个重复,不用担心,这个程序能帮你找到重复文件;想怎么批量删除,有你说了算!
具有图形界面的便捷工具,可删除/删除文本文件中的重复行。
%%**************************************************** **************************************************** % 名称:Get_Duplicate_array_with_Index %作者:Pruthvi Raj G-KPIT_RNTBCI ::(9677066394 :: ...
$ npm install array-duplicate 用法 var array1 = [ 1 , 2 , 3 ] var array2 = [ 2 , 3 , 4 ] duplicated ( array1 , array2 ) // yeilds [2, 3] 执照 版权所有(c)2015 ,已获得MIT Expat许可。
删除重复项目标:此分配的目的是使用迭代器或使用诸如Set内置对象从数组中删除重复项。...Add the remote to the starter codegit remote add starter ...问题如果有任何问题,在处提出问题
使用RMAN DUPLICATE...FROM ACTIVE DATABASE 创建物理备库 简化standby创建过程,提高效率
3. Remove any product identification, copyright, proprietary notices or labels from Vistanita Duplicate Finder. 4. Distribute, re-distribute, rent, lease or sell the licensed version of Vistanita ...
删除重复邮件,非常好用,使用前务必先关闭OUTLOOK,进去后就好了
Duplicate Cleaner Pro v4.1.4_Portable,windows下的非常好用的文件去重工具,可以精确删除磁盘上的重复文件,释放空间。SN:1111111111
-Python script to remove whole duplicate fasta sequences i.e identical sequence and header -input file must be in fasta format usage: python remove_duplicate_fasta.py inputfile outputfile 例子: ...
remove_duplicate_files 我有许多包含类似文件的备份。 为了确保我只检查了一次文件,我编写了这个脚本来删除任何重复项。 如果文件位于相同位置,相对于搜索目录,并且具有相同的二进制内容,则文件被视为重复。 ...