发表于 | 分类于 ，
字数统计: | 阅读时长 ≈

快速排序

挖坑填数+分治法

快排的思想就是:

  • 头尾指针,挖坑填数,确定一个元素,它的左边元素都比它大,右边元素都比它小
  • 递归,保证每一个子列表都满足它的左边元素都比它大,右边元素都比它小,这样就是有序的

为什么要用分治法?

根源是:一次挖坑排序,只能确保

https://blog.csdn.net/MoreWindows/article/details/6684558

可以使用分治的保障是?

每次会返回一个middle值,这个值,左边的都比他小,右边的都比他大

这样才能保证调整到最后整个数组有序

挖坑:
不需要担心数据被覆盖,因为数据都已经被保存了.

对挖坑填数进行总结

1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。

2．j–由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。

3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。

4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。

递归实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class QuickSort {
    private static void quickSort(int[] a, int low, int high) {
        /**
         * void: 没有返回值是因为操作数组,直接交换值
         * low,high: 是为了递归
         */
        // 递归的结束条件
        if (low >= high) {
            return;
        }
        int i, j, tmp;
        // 保留low,high为了后面的递归
        i = low;
        j = high;
        // 挖坑
        tmp = a[low];
        while (i < j) {
            while (i < j && a[j] >= tmp) {
                j--;
            }
            if (i < j) {
                a[i++] = a[j];
            }
            while (i < j && a[i] < tmp) {
                i++;
            }
            if (i < j) {
                a[j--] = a[i];
            }
        }
        // 此时i=j
        a[i] = tmp;
        quickSort(a, low, i - 1);
        quickSort(a, i + 1, high);
    }

    public static void main(String[] args) {

        int[] a = {49, 38, 65, 97, 76, 13, 27, 49};
        System.out.println(Arrays.toString(a));
        quickSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));

    }
}

将中间一部分抽出来,可以看到就是一个典型的递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class QuickSort {
    private static void quickSort(int[] a, int low, int high) {
        if (low >= high) {
            return;
        }
        int i = adjustArray(a, low, high);
        quickSort(a, low, i - 1);
        quickSort(a, i + 1, high);
    }

    private static int adjustArray(int[] a, int low, int high) {
        int tmp = a[low];
        while (low < high) {
            while (low < high && a[high] >= tmp) {
                high--;
            }
            if (low < high) {
                a[low++] = a[high];
            }
            while (low < high && a[low] < tmp) {
                low++;
            }
            if (low < high) {
                a[high--] = a[low];
            }
        }
        a[low] = tmp;
        return low;
    }

    public static void main(String[] args) {

        int[] a = {49, 38, 65, 97, 76, 13, 27, 49};
        System.out.println(Arrays.toString(a));
        quickSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));

    }
}

python:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
def adjust_array(low, high):
    temp = a[low]
    while low < high:
        while low < high and a[high] >= temp:
            high -= 1
        if low < high:
            a[low] = a[high]
            low += 1
        while low < high and a[low] <= temp:
            low += 1
        if low < high:
            a[high] = a[low]
            high -= 1

    a[low] = temp
    return low


def quick_sort(low, high):
    if low >= high:
        return
    mid = adjust_array(low, high)
    quick_sort(low, mid - 1)
    quick_sort(mid + 1, high)
    pass


if __name__ == '__main__':
    a = [5, 4, 5, 7, 9, 2, 1]
    quick_sort(0, len(a) - 1)
    print(a)

发表于
字数统计: | 阅读时长 ≈

python

range 用法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
>>> a=10
>>> for i in range(10)[::-1]:
...     print(i)
...
9
8
7
6
5
4
3
2
1
0
>>>

for循环

1
2
3
4
5
6
7
for(int i=0;i<10;i++){
    ......
}

for(int i=10;i>0;i--){
    ......
}

等价于:

1
2
3
4
for i in range(10):
    .....
for i in range(10)[::-1]:
    .....

发表于 | 分类于 ，
字数统计: | 阅读时长 ≈

179

Given a list of non negative integers, arrange them such that they form the largest number.

Example 1:

1
2
3
Input: [10,2]
Output: "210"
Example 2:
1
2
Input: [3,30,34,5,9]
Output: "9534330"

Note: The result may be very large, so you need to return a string instead of an integer.

思路

关键点就在于，如何对比两个数的大小？（理解为两个数谁应该放在前面），解法是按照顺序拼接两个字母串进行比较，如果a ＋b串 大于 b＋a串，那么a比较大（即题意中理解的a应该放在前面），反之b比较大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        if len(nums)==0:
            return ""
        self.quickSort(nums,0,len(nums)-1)
        return str(int("".join(map(str, nums)))) 


    def compare(self,num1:int,num2:int):
        return str(num1)+str(num2)>str(num2)+str(num1)

    def quickSort(self,nums: List[int],low: int,high:int):
        if low >=high:
            return
        mid = self.adjust(nums,low,high)
        self.quickSort(nums,low,mid-1)
        self.quickSort(nums,mid+1,high)
    
    def adjust(self,nums: List[int],l:int,r:int) -> int:
        low = l
        while l < r:
            if self.compare(nums[l], nums[r]):
                nums[l], nums[low] = nums[low], nums[l]
                low += 1
            l += 1
        nums[low], nums[r] = nums[r], nums[low]
        return low

发表于 | 分类于 ，
字数统计: | 阅读时长 ≈

242

Given two strings s and t , write a function to determine if t is an anagram of s.

Example 1:

1
2
Input: s = "anagram", t = "nagaram"
Output: true

Example 2:

1
2
Input: s = "rat", t = "car"
Output: false

Note:
You may assume the string contains only lowercase alphabets.

Follow up:
What if the inputs contain unicode characters? How would you adapt your solution to such case?

题目意思

比较两个字符串包含的字符是否相同

解题

  • 先将字符排序,然后比较
1
2
3
4
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
       return sorted(s) == sorted(t) 
`
  • 如果都是字母组成,可以统计字母的个数,然后比较
1
2
3
4
5
6
7
8
class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        dict1,dict2 = {},{}
        for item in s:
            dict1[item] = dict1.get(item,0)+1
        for item in t:
            dict2[item] = dict2.get(item,0)+1
        return dict1 == dict2

发表于 | 分类于 ，
字数统计: | 阅读时长 ≈

148

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

1
2
Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

1
2
Input: -1->5->3->4->0
Output: -1->0->3->4->5

思路: O(nlogn)采用归并排序

总结,归并排序的本质是两个有序数组排序

{cmd
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

class ListNode:
    def __init__(self, val):
        self.val, self.next = val, None


class LinkList:
    def __init__(self):
        self.head = None

    def init_list(self, data):
        assert type(data) == list
        if data:
            point = self.head = ListNode(data[0])
            for i in data[1:]:
                point.next = ListNode(i)
                point = point.next
        return self.head

    @staticmethod
    def print_list(head):
        data = []
        while head:
            data.append(str(head.val))
            head = head.next
        print("->".join(data))

class Solution(object):
    def merge(self, h1, h2):
        dummy = tail = ListNode(None)
        while h1 and h2:
            if h1.val < h2.val:
                tail.next, tail, h1 = h1, h1, h1.next
            else:
                tail.next, tail, h2 = h2, h2, h2.next

        tail.next = h1 or h2
        return dummy.next

    def sortList(self, head):
        if not head or not head.next:
            return head

        pre, slow, fast = None, head, head
        while fast and fast.next:
            pre, slow, fast = slow, slow.next, fast.next.next
        pre.next = None

        return self.merge(*map(self.sortList, (head, slow)))



if __name__ == '__main__':
    data = [4, 6, 1, 3, 4, 2]
    link_list = LinkList()
    link_list.init_list(data)
    print("example:")
    link_list.print_list(link_list.head)
    print("result:")
    result = Solution().sortList(link_list.head)
    link_list.print_list(result)

知识点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
def sortList(self, head):
    if not head or not head.next:
        return head

    pre, slow, fast = None, head, head
    while fast and fast.next:
        pre, slow, fast = slow, slow.next, fast.next.next
    pre.next = None

    return self.merge(*map(self.sortList, (head, slow))

等价于:
def sortList(self, head):
    if not head or not head.next:
        return head

    pre, slow, fast = None, head, head
    while fast and fast.next:
        pre, slow, fast = slow, slow.next, fast.next.next
    pre.next = None

    left = self.sortList(head)
    right = self.sortList(slow)
    return self.merge(left, right)
  1. map函数的原型是map(function, iterable, …)，它的返回结果是一个列表,函数式编程
{cmd
1
2
3
4
def mul(x):
    return x*x
res=map(mul,(1,2))
print(res)
  1. (*)号操作符
{cmd
1
2
3
4
def add(a,b):
    print(a+b)
l= [1,2]
add(*l)
  1. 排序时间复杂度
排序方法 平均时间 最好时间 最坏时间
桶排序(不稳定) O(n) O(n) O(n)
基数排序(稳定) O(n) O(n) O(n)
归并排序(稳定) O(nlogn) O(nlogn) O(nlogn)
快速排序(不稳定) O(nlogn) O(nlogn) O(n^2)
堆排序(不稳定) O(nlogn) O(nlogn) O(nlogn)
希尔排序(不稳定) O(n^1.25)
冒泡排序(稳定) O(n^2) O(n) O(n^2)
选择排序(不稳定) O(n^2) O(n^2) O(n^2)
直接插入排序(稳定) O(n^2) O(n) O(n^2)
  1. 归并排序
    思路:分解->两个子序列排序
    4.1. 如何分解,及如何递归的解决这个问题
    4.2. 两个子序列排序

发表于 | 分类于 ，
字数统计: | 阅读时长 ≈

题意：

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

解题思路:

  1. 先将区间按照每个start的值来排序，(所给数据是乱序)
  2. 排好序以后判断一个区间的start值是否处在前一个区间中，如果在前一个区间中，那么合并；如果不在，就将新区间添加。
1
2
3
4
5
6
7
8
def merge(self, intervals):
    out = []
    for i in sorted(intervals, key=lambda i: i.start):
        if out and i.start <= out[-1].end:
            out[-1].end = max(out[-1].end, i.end)
        else:
            out += i,
    return out

https://zhuanlan.zhihu.com/p/33114095

总结:

  1. sorted 函数
    http://www.runoob.com/python/python-func-sorted.html
  2. lambda 表达式
    https://www.jianshu.com/p/9f306285a3ca

发表于 | 分类于 ，
字数统计: | 阅读时长 ≈

57

  1. 简单的for…[if]…语句

for…[if]…语句一种简洁的构建List的方法，从for给定的List中选择出满足if条件的元素组成新的List，其中if是可以省略的

1
2
3
4
>>> a=[1,2,3,4,5,6]
>>> b=[x for x in a if x%2==0]
>>> b
[2, 4, 6]

https://blog.csdn.net/gzhouc/article/details/53240749

发表于 | 分类于 ，
字数统计: | 阅读时长 ≈

题目

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

1
2
3
4
5
6
7
Input: [5,2,6,1]
Output: [2,1,1,0] 
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

判断数组某个元素右边有几个比他小的

思路

Brute force

最容易想到的:

1
2
3
4
5
6
7
8
class Solution:
    def countSmaller(self, nums: List[int]) -> List[int]:
        count = [0]*len(nums)
        for i in range(len(nums)):
            for j in range(len(nums))[i+1:]: 
                if nums[j]<nums[i]:
                    count[i] +=1
        return count

时间复杂度O(n2)太大.

1
2
Time Limit Exceeded
15/16 cases passed (N/A)

Fenwick Tree/ Binary Indexed Tree(BST)

逆序

归并排序

以[5, 2, 6, 1]为例，我们使用归并排序解决这个问题：
首先归并排序将[5, 2, 6, 1]分为

[5, 2], [6, 1]

然后因为再归并的话可以得到

[[5], [2]], [[6], [1]]

在[[5], [2]]中，[2]位于整个区间的右部，所以结果为0；[5]位于左边，使[5]中每个元素都与右边[2]比较，可以得到5的count值为1；比较完成后对[[5], [2]]进行排序，得到：

[[5(1)], [2]], [[1], [6]]

然后在[[1], [6]]中执行相同的操作，1的count值为0， 6的count值为1，得到：

[[2], [5(1)]], [[1], [6(1)]]

然后在[[[2], [5(1)]], [[1], [6(1)]]]中进行比较，左边[[2], [5(1)]]中每个数值都在[[1], [6(1)]]进行遍历计数，由于[[1], [6(1)]]和[[2], [5(1)]]都已经排好序了，所以只需要遍历一遍就可以得到结果：

[[2(1)], [5(2)]], [[1], [6(1)]]

每次通过辅助的拷贝数组将计数信息保存到正确的位置即可；
由于使用了归并排序，所以每次进行比较的时候都是比较的有序队列，这样可以很好地提高效率，同时也保证了每一轮次左右相对位置的稳定；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def countSmaller(nums):
    def sort(enum):
        half = int(len(enum) / 2)
        if half:
            left, right = sort(enum[:half]), sort(enum[half:])
            for i in range(len(enum))[::-1]:
                print(i)
                # left[-1][1]: 左边最后一个元素的值,right[-1][1]: 右边最后一个元素的值
                # 由于子序列是有序的，左边元素最小，右边元素最大
                print("left:", left)
                print("right:", right)
                # 因为不停弹出数据，所以left，right有可能为空的情况
                if not right or left and left[-1][1] > right[-1][1]:
                    # 使用pop，每次弹出最后一个元素
                    smaller[left[-1][0]] += len(right)
                    enum[i] = left.pop()
                else:
                    enum[i] = right.pop()
        print("enum", enum)
        print("smaller:", smaller)
        print("=============")
        return enum

    smaller = [0] * len(nums)
    # 虽然数组有序的，但是原始顺序变化了,计算每个元素数量需要找到他们的位置，因此需要记录每个元素的index
    sort(list(enumerate(nums)))
    return smaller


if __name__ == '__main__':
    nums = [5, 2, 6, 1]
    print("input:", nums)
    smaller = countSmaller(nums)
    print("output:", smaller)

参考文档