摘要：写在前面今天的小李的目标是排序算法，果然还是要下手写才会更有体会，也更记得住。排序算法冒泡排序主要是比对相邻两个数之间的大小关系，不断将较大值交换至最后。
写在前面
今天的小李的目标是排序算法，果然还是要下手写才会更有体会，也更记得住。
认真做题的分割线215. 数组中的第K个最大元素
难度：中等
在未排序的数组中找到第k个最大的元素。请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
我的题解:
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
num = quicksort(nums,0,len(nums)-1)
return num[len(nums)-k]
def quicksort(v,start,end):
if start < end:
i,j = start,end
base = v[i]
while i < j:
while i < j and v[j] >= base:
j -= 1
v[i] = v[j]
while i < j and v[i] < base:
i +=1
v[j] = v[i]
v[i] = base
quicksort(v,start,i-1)
quicksort(v,j+1,end)
return v
我的思路:
通过快速排序算法,对数据进行排序后,找到对应的值.
排序算法:
快排的主体思路是,找到对应的标杆值,然后对标杆值两侧进行划分,然后分而治之,对两侧再进行递归的切分标杆值.
所以常见的是递归的思路.
之前看《算法图解》的代码，今晚尝试了下：
def quicksort(array):
if len(array) < 2:
return array
temp = array[0]
less = [ i for i in array[1:] if i <= temp]
greater = [i for i in array[1:] if i > temp]
return quicksort(less) + temp + quicksort(greater)
比较能够明显的显示快排的思路，但是这个效率并不高，因为每次递归都需要对两侧的数组进行一次硬性排序。
且return 不支持不同类型（list和int）一起。
优化后，我们采用的方式是加入了start和end的参数，依然是对标杆值两侧进行划分，但是会减少排序重复量，降低了复杂度。
215. 数组中的第K个最大元素
难度：中等
给定一个非空的整数数组，返回其中出现频率前k高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
说明：
你可以假设给定的k总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于O(n log n), n 是数组的大小。
我的题解:
class Solution(object):
def topKFrequent(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
l = dict()
res = []
for i in nums:
if i in l:
l[i] += 1
else:
l[i] = 1
items = list(l.items())
items.sort(key = lambda x:x[1],reverse = True)
for i in range(k):
res.append(items[i][0])
return res
我的思路:
这题按正常题解，应该使用桶排序。
我用的方案是用hash表记录对应的值，然后将hash表转成二维list，并对二级域进行排序。
然后输出对应值。
其他:
这题要再尝试下桶排序的方式，主要是对sort()函数参数有了新的认识。
sorted(iterable[, cmp[, key[, reverse]]])
iterable指定要排序的list或者iterable
cmp为函数，指定排序时进行比较的函数，可以指定一个函数或者lambda函数
key为函数，指定取待排序元素的哪一项进行排序，用于指定哪一个域
215. 数组中的第K个最大元素
难度：中等
给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。
示例 1:
输入: [10,2]
输出: 210
示例 2:
输入: [3,30,34,5,9]
输出: 9534330
说明: 输出结果可能非常大，所以你需要返回一个字符串而不是整数。
我的题解:
class Solution(object):
def largestNumber(self, nums):
"""
:type nums: List[int]
:rtype: str
"""
l = len(nums)
i = l
#比较a+b 和 b+a
while i > 0:
for j in range(i-1):
a = nums[j]
b = nums[j+1]
ab = int(str(a)+str(b))
ba = int(str(b)+str(a))
if ab < ba:
nums[j],nums[j+1] = nums[j+1],nums[j]
i -=1
res= ""
for n in nums:
if res == "" and n == 0:
continue
res += str(n)
if res == "":
return "0"
return res
我的思路:
这题参考了小佳扬的写法，主要是使用了冒泡排序。
但属于自定义的冒泡排序，每次都比对字符串前后排序不同时得出的结果哪个更大，会获得的更大值需要放在更前，相反则放后。
排序算法:
冒泡排序主要是比对相邻两个数之间的大小关系，不断将较大值交换至最后。
明天要继续攻略排序算法。
纸上得来终觉浅，绝知此事要躬行。
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/43661.html
摘要：刷题第三天正式刷题第三天。注意空字符串可被认为是有效字符串。错误的一次是因为没有考虑空字符串，当存在为的时候，结果应该为。第二题加一难度简单类型给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。 刷题第三天 正式刷题第三天。之前看了个说法，挺认可的。就是不要太在意一天的能呈现的价值，但是要在意累计的价值。之前很多时候我会对今天一天没有完成的计划而沮丧，事实上，算法的实践...
摘要：第五题对称二叉树难度简单给定一个二叉树，检查它是否是镜像对称的。第十六题最大连续的个数难度简单给定一个二进制数组，计算其中最大连续的个数。第十八题平方数之和难度简单给定一个非负整数，你要判断是否存在两个整数和，使得。 写在前面 最近忙着调教新装备，没有及时的写题解，但是没有在偷懒没刷题喔~来认真整理下最近做的题目~ 之前考虑按tag来刷题，后来收到了推荐的leetcode题解，就根据上...
摘要：写在前面的话好几天木有刷题啦，今天猛刷了一把，要梳理一个顺序好好的学习啦一定要好好执行每天做题的计划最近真的好忙碌啊，还要做视频。第二题最大子序和难度简单给定一个整数数组，找到一个具有最大和的连续子数组子数组最少包含一个元素，返回其最大和。 写在前面的话 好几天木有刷题啦，今天猛刷了一把，要梳理一个顺序好好的学习啦~一定要好好执行每天做题的计划！最近真的好忙碌啊，还要做视频。不过呢，看...
摘要：写在前面今天没有叨逼叨但是又一次错过了竞赛爱睡觉的小李下周要上班，下下周一定要参加了握拳认真做题的分割线第一题两地调度公司计划面试人。第人飞往市的费用为，飞往市的费用为。示例输入输出解释第一个人去市，费用为。 写在前面 今天没有叨逼叨...但是又一次错过了竞赛...爱睡觉的小李...下周要上班，下下周一定要参加了（握拳 认真做题的分割线 第一题 1029. 两地调度公司计划面试2N人。...
摘要：第二题汉明距离难度简单两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给出两个整数和，计算它们之间的汉明距离。第三题买卖股票的最佳时机难度简单给定一个数组，它的第个元素是一支给定股票第天的价格。 写在前面 这几天断断续续做了题目，也在慢慢体会一些数据思维。终于不用边做视频边写题目啦~开心~把这几天的题解发一下~ 认真做题的分割线 第一题 977. 有序数组的平方难度...
阅读 2227·2021-11-15 11:39
阅读 981·2021-09-26 09:55
阅读 924·2021-09-04 16:48
阅读 2830·2021-08-12 13:23
阅读 918·2021-07-30 15:30
阅读 2454·2019-08-29 14:16
阅读 884·2019-08-26 10:15
阅读 525·2019-08-23 18:40
