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