楼市新闻、行业动态
叭楼，新房带看，二手房代办过户，望京二手房精选房源，您置业的小管家。
排序的题目较少，简单题和中等题写在一篇，一共9个题。
提纲
56. 合并区间
75. 颜色分类
147. 对链表进行插入排序
148. 排序链表
179. 最大数
220. 存在重复元素 III
242. 有效的字母异位词
274. H指数
324. 摆动排序 II
56. 合并区间
给出一个区间的集合，请合并所有重叠的区间。
示例 :
输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].思路
先按区间的第一个元素大小进行排序，然后将第一个区间放入res列表中， 如果当前区间的第一个数比res中最后一个区间的第二个数小，则更新结果中的最后一个区间，否则，将当前区间加入结果列表中。
代码
class Solution(object):
def merge(self, intervals):
"""
:type intervals: List[List[int]]
:rtype: List[List[int]]
"""
if len(intervals) <= 1:
return intervals
intervals.sort(key=lambda x:x[0]) # 根据每个区间的第一个数对列表排序
res = [intervals[0]] # 用于保存得到的结果
for i in range(1, len(intervals)):
if intervals[i][0] <= res[-1][1]:
res[-1][1] = max( res[-1][1], intervals[i][1])
else:
res.append(intervals[i])
return res75. 颜色分类
给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
注意:
不能使用代码库中的排序函数来解决这道题。
示例:
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]思路
三路快排，0移动到最左边，2移动到最右边，遇到1则跳过。
代码
class Solution(object):
def sortColors(self, nums):
"""
:type nums: List[int]
:rtype: None Do not return anything, modify nums in-place instead.
"""
left = 0
right = len(nums) - 1
i = 0
while i <= right:
if nums[i] == 2:
nums[i], nums[right] = nums[right], nums[i]
right -= 1
elif nums[i] == 0:
nums[i], nums[left] = nums[left], nums[i]
left += 1
i += 1
else:
i += 1147. 对链表进行插入排序
对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
插入排序算法：
- 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
- 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
- 重复直到所有输入数据插入完为止。
示例 ：
输入: 4->2->1->3
输出: 1->2->3->4思路
用指针p逐一向后遍历，申请一个虚拟头结点dummyHead，指向头结点，便于在头结点插入。当p的值小于等于下一个结点的值，指针p右移；当p的值大于下一节点的值，那么将p的下一个节点取出，从前往后扫描，在第一个比它的值大的节点之前插入该节点。
代码
class Solution(object):
def insertionSortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:
return head
dummyHead = TreeNode(0)
dummyHead.next = head
p = head
while p.next:
if p.val <= p.next.val:
p = p.next
else:
temp = p.next
q = dummyHead
p.next = p.next.next
while q.next and q.next.val < temp.val:
q = q.next
temp.next = q.next
q.next = temp
return dummyHead.next148. 排序链表
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
示例 :
输入: 4->2->1->3
输出: 1->2->3->4思路
使用归并排序。使用快慢指针寻找链表中点，并分解链表；递归融合两个有序链表。
代码
class Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if head is None:
return None
return self.minute(head)
def minute(self, head):
"""
快慢指针分解链表
"""
if head.next is None:
return head
quick, slow, temp = head, head, head
while quick is not None and quick.next is not None:
temp = slow
slow = slow.next
quick = quick.next.next
temp.next = None # 这一步就是将整个链表从中间分开 失去这一步 后面将无限循环
i = self.minute(head)
j = self.minute(slow)
return self.Combined(i, j)
def Combined(self, i, j):
"""
合的过程就是从i 和 j开始比较 就是从开头和中间开始比较 将两个相比小的排在head后
最后返回head即可
"""
TempNode = ListNode(0)
temp = TempNode
while i is not None and j is not None:
if i.val <= j.val:
temp.next = i
i = i.next
else:
temp.next = j
j = j.next
temp = temp.next
if i is not None:
temp.next = i
if j is not None:
temp.next = j
return TempNode.next179. 最大数
给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。
示例 :
输入: [3,30,34,5,9]
输出: 9534330思路
如何比较两个数合并后的大小，顺序拼接两个字符串，如果a+b>b+a，那么a在前面。
代码
class Solution(object):
def largestNumber(self, nums):
"""
:type nums: List[int]
:rtype: str
"""
def compare(a,b):
return int(b + a) - int(a + b)
nums = sorted([str(i) for i in nums],cmp = compare)
ans = ''.join(nums).lstrip('0') #lstrip是去除左边的0
return ans or '0'220. 存在重复元素 III
给定一个整数数组，判断数组中是否有两个不同的索引 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值最大为 t，并且 i 和 j 之间的差的绝对值最大为 。
示例 1:
输入: nums = [1,2,3,1], k= 3, t = 0
输出: true示例 2:
输入: nums = [1,0,1,1], k=1, t = 2
输出: true示例 3:
输入: nums = [1,5,9,1,5,9], k = 2, t = 3
输出: false思路
将数值依次放入set中，当长度>k，就把set中最左边的元素删除。
代码
class Solution(object):
def containsNearbyAlmostDuplicate(self, nums, k, t):
"""
:type nums: List[int]
:type k: int
:type t: int
:rtype: bool
"""
a = set()
for i in range(len(nums)):
if t == 0:
if nums[i] in a:
return True
else:
for item in a:
if abs(nums[i] - item) <= t:
return True
a.add(nums[i])
if len(a) == k+1:
a.remove(nums[i - k])
return False242. 有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true示例 2:
输入: s = "rat", t = "car"
输出: false思路
考虑字母出现的频率是否相等。首先，两个字符串长度不相等，返回False；然后将字符串s放在set中，消除重复元素，遍历这些元素，如果s中字母的个数和t中字母的个数不相等，返回False。
代码
class Solution(object):
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
if len(s) != len(t):
return False
for i in set(s):
if s.count(i) != t.count(i):
return False
return True274. H指数
给定一位研究者论文被引用次数的数组（被引用次数是非负整数）。编写一个方法，计算出研究者的 h 指数。
h 指数的定义: “h 代表“高引用次数”（high citations），一名科研人员的 h 指数是指他（她）的 （N 篇论文中）至多有 h 篇论文分别被引用了至少 h 次。（其余的 N – h 篇论文每篇被引用次数不多于 h 次。）”
示例：
输入: citations = [3,0,6,1,5]
输出: 3
解释: 给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
由于研究者有 3 篇论文每篇至少被引用了 3 次，其余两篇论文每篇被引用不多于 3 次，所以她的 h 指数是 3。思路
将数组从小到大排序，遍历数组，判断当前值是否满足H指数。
代码
class Solution(object):
def hIndex(self, citations):
"""
:type citations: List[int]
:rtype: int
"""
citations.sort() #从小到大排列
h = len(citations)
index = 0
while index < len(citations):
if citations[index] >= h:
return h
index += 1
h -=1
return 0324. 摆动排序 II（*）
给定一个无序的数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。
示例 :
输入: nums = [1, 5, 1, 1, 6, 4]
输出: 一个可能的答案是 [1, 4, 1, 5, 1, 6]思路
对数组进行排序，奇数索引位置放入大于中位数的数，偶数索引放入小于中位数的数，穿插排序。
代码
class Solution(object):
def wiggleSort(self, nums):
nums.sort()
half = len(nums[::2])
nums[::2], nums[1::2] = nums[:half][::-1], nums[half:][::-1]声明：本站内容来源于网络或叭楼会员发布，叭楼只作为信息发布平台，版权归原作者所有，本站不承担任何图片、内容、观点等内容版权问题，如对内容有歧义，可第一时间联系本站管理员发送邮件8309272@qq.com或者扫码微信沟通，经核实后我们会第一时间删除。
北京二手房、楼市分析
排序的题目较少，简单题和中等题写在一篇，一共9个题。提纲56. 合并区间75. 颜色分类147. 对链表进行插入排序148. 排序链表179. 最大数220. 存在重复元素 III242. 有效的字母异位词274. H指数324. 摆动排序 II56. 合并区间给出一个区间的集合，请合并所有重…
暂无评论内容