写在前面
今天的小李的目标是排序算法，果然还是要下手写才会更有体会，也更记得住。
认真做题的分割线
第一题
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
我的思路:
这题参考了小佳扬的写法，主要是使用了 冒泡排序 。
但属于自定义的冒泡排序，每次都比对字符串前后排序不同时得出的结果哪个更大，会获得的更大值需要放在更前，相反则放后。
排序算法:冒泡排序 主要是比对相邻两个数之间的大小关系，不断将较大值交换至最后。
总结
明天要继续攻略排序算法。
纸上得来终觉浅，绝知此事要躬行。