- 浏览: 173449 次
- 性别:
- 来自: 济南
文章分类
最新评论
之前介绍过在排好序的链表中删除节点,只需要遍历一遍链表,所以时间复杂度为O(n)。这篇文章讨论对无序链表的去重问题。
给定一个无序链表,删除里面的重复元素,我们用bruce force来进行的话时间复杂度为O(n^2),我们从头节点开始判断,如果有相等的元素,就将当前节点的next指向下一个节点的next。每个元素都要遍历一次它们后面的元素。代码如下:
我们也可以先用归并排序将链表排序,然后在去重,这样事件复杂度为O(n + nlogn), 也就是O(nlogn)。代码如下:
给定一个无序链表,删除里面的重复元素,我们用bruce force来进行的话时间复杂度为O(n^2),我们从头节点开始判断,如果有相等的元素,就将当前节点的next指向下一个节点的next。每个元素都要遍历一次它们后面的元素。代码如下:
public ListNode deleteDuplicates(ListNode head) { if(head == null) return head; ListNode current = head; while(current != null) { int value = current.val; ListNode find = current; while(find.next != null) { if(find.next == value) { find.next = find.next.next; } else { find = find.next; } } current = current.next; } return head; }
我们也可以先用归并排序将链表排序,然后在去重,这样事件复杂度为O(n + nlogn), 也就是O(nlogn)。代码如下:
public class DeleteDuplicate { public ListNode deleteDupli(ListNode head) { if(head == null) return null; ListNode helper = sort(head); while(head.next != null) { if(head.val == head.next.val) { head.next = head.next.next; } else { head = head.next; } } return helper; } public ListNode sort(ListNode head) { if(head == null || head.next == null) return head; ListNode fast = head; ListNode slow = head; while(fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next; } ListNode next = slow.next; slow.next = null; ListNode a = sort(next); ListNode b = sort(head); return merge(a, b); } public ListNode merge(ListNode a, ListNode b) { if(a == null) return b; if(b == null) return a; if(a.val > b.val){ b.next = merge(a, b.next); return b; } else { a.next= merge(a.next, b); return a; } } }
发表评论
-
498. Diagonal Traverse
2019-11-15 13:52 227Given a matrix of M x N eleme ... -
496 Next Greater Element I
2019-11-14 13:50 226You are given two arrays (witho ... -
Word Break II
2016-03-09 03:15 342Given a string s and a dictiona ... -
Insert Interval
2016-03-08 02:11 333Given a set of non-overlapping ... -
Merge Intervals
2016-03-07 05:25 451Given a collection of intervals ... -
Merge k Sorted Lists
2016-03-07 04:03 512Merge k sorted linked lists and ... -
Multiply Strings
2016-03-06 07:27 430Given two numbers represented a ... -
N-Queens II
2016-03-06 03:06 620Follow up for N-Queens problem. ... -
N-Queens
2016-03-06 02:47 428The n-queens puzzle is the prob ... -
First Missing Positive
2016-03-05 03:09 388Given an unsorted integer array ... -
Spiral Matrix
2016-03-04 03:39 519Given a matrix of m x n element ... -
Trapping Rain Water
2016-03-04 02:54 532Given n non-negative integers r ... -
Repeated DNA Sequences
2016-03-03 03:10 371All DNA is composed of a series ... -
Increasing Triplet Subsequence
2016-03-02 02:48 861Given an unsorted array return ... -
Maximum Product of Word Lengths
2016-03-02 01:56 883Given a string array words, fin ... -
LRU Cache
2016-02-29 10:37 555Design and implement a data str ... -
Super Ugly Number
2016-02-29 07:07 601Write a program to find the nth ... -
Longest Increasing Path in a Matrix
2016-02-29 05:56 764Given an integer matrix, find t ... -
Coin Change
2016-02-29 04:39 735You are given coins of differen ... -
Minimum Height Trees
2016-02-29 04:11 629For a undirected graph with tre ...
相关推荐
Oracle 11gR2 使用 RMAN duplicate from active database 复制数据库
删除重复 去重复url 删除重复网址 remove duplicate url 一个国外的删除重复网址软件
获取从index=1及之后的数据 ${fromlist} Get Slice From List ${list} 1 # 获取从index=1~2的数据,不包括第3个 ${fromtolist} Get Slice From List ${list} 1 3 4 Remove Duplicates-去重 ⽰例: @{list} Create ...
public static void removeDuplicate(List list) { for ( int i = 0 ; i < list.size() - 1 ; i ++ ) { for ( int j = list.size() - 1 ; j > i; j -- ) { if (list.get(j).equals(list.get(i))) { list....
LeetCode Remove Duplicates from Sorted Array解决方案
具有图形界面的便捷工具,可删除/删除文本文件中的重复行。
删除重复项目标:此分配的目的是使用迭代器或使用诸如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,进去后就好了
remove_duplicate_files 我有许多包含类似文件的备份。 为了确保我只检查了一次文件,我编写了这个脚本来删除任何重复项。 如果文件位于相同位置,相对于搜索目录,并且具有相同的二进制内容,则文件被视为重复。 ...
语言:English删除重复电子邮件以进行快速营销删除重复电子邮件以进行快速营销
FirmTools Duplicate Photo Finder 相似图像查询软件 你电脑中如果有很多图像,有很多可能是一个logo只差,你用其他md5检测软件是不能快速找出来的。这个软件可以搜索相似的图像,你查看后选择删除,非常的方便。 ...
Fast Duplicate File Finder
duplicate绝对干货。利用duplicate复制数据库,文档中包换每一步的试验步骤,详细说明了每一步的作用及用途,和注意事项,一步一步至试验成功,绝对一次成功。
duplicate cleaner pro 破解版 4.0.5 。安装后,将第二步的x86及x64目录下的文件拷贝到安装目录下的x86与x64下。然后启动,输入长一点的序列号(随便输入字符),即可破解。
Oracle RMAN DUPLICATE教程
Rman通过duplicate创建standby
Duplicate File Finder单文件