排序

发表于 | 分类于 ，

十大排序

题目一：922. 按奇偶排序数组 II

给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。

对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。

你可以返回任何满足上述条件的数组作为答案。

示例：

1
2
3
输入：[4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受

提示：

  1. 2 <= A.length <= 20000
  2. A.length % 2 == 0
  3. 0 <= A[i] <= 1000

思路：奇偶下标的错误数进行交换。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def sortArrayByParityII(A):
    if not A:
        return []
    even , odd = 0 , 1
    while even < len(A) and odd < len(A):
        ##一旦两个下标的数不对，则交换
        if A[even] % 2 and A[odd] % 2 == 0:
            A[even] , A[odd] = A[odd] , A[even]
            even += 2
            odd += 2
        elif A[even] % 2 == 0 and A[odd] % 2:
            even += 2
            odd += 2
        elif A[even] % 2 == 0 and A[odd] % 2 == 0:
            even += 2
        elif A[even] % 2 and A[odd] % 2 :
            odd += 2
    return A

题目二：349. 两个数组的交集

给定两个数组，编写一个函数来计算它们的交集。

示例 1:

1
2
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]

示例 2:

1
2
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]

说明:

  • 输出结果中的每个元素一定是唯一的。
  • 我们可以不考虑输出结果的顺序。

思路一：采用字典，时间O（m+n)，空间O（min(m,n)）

​ 采用字典存储nums1的数，然后遍历nums2的数，一旦在字典中则加入结果中

代码：

1
2
3
4
5
6
7
8
9
10
11
12
from collections import Counter
class Solution:
    def intersection(self, nums1, nums2):
        if not nums1 or not nums2:
            return nums1 if nums2 else nums2
        res = []
        n1 , n2 = len(nums1) , len(nums2)
        counter1 = Counter(nums1)
        for num in nums2:
            if num in counter1:
                res.append(num)
        return list(set(res))

思路二：排序，时间O(mn)，空间O（1）

​ 对两个数组进行排序，同时遍历两个数组

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def intersection(self, nums1, nums2):
        snum1 = sorted(nums1)
        snum2 = sorted(nums2)
        res = []
        i , j = 0 , 0
        while i < len(snum1) and j < len(snum2):
            if snum1[i] == snum2[j]:
                res.append(snum2[j])
                i += 1
                j += 1
            elif snum1[i] < snum2[j]:
                i += 1
            else:
                j += 1
        return list(set(res))

思路三：采用集合交集特性，平均时间O（min(m,n))，最坏时间O（m*n)，空间O（m+n)

代码

1
2
3
4
5
6
7
8
9
10
11
12
def intersection(nums1, nums2):
    """
    :type nums1: List[int]
    :type nums2: List[int]
    :rtype: List[int]
    """
    if not nums1 or not nums2:
        return []
    else:
        a=set(nums1)
        b=set(nums2)
        return list(a&b)

题目三：976. 三角形的最大周长

给定由一些正数（代表长度）组成的数组 A，返回由其中三个长度组成的、面积不为零的三角形的最大周长。

如果不能形成任何面积不为零的三角形，返回 0。

示例 1：

1
2
输入：[2,1,2]
输出：5

示例 2：

1
2
输入：[1,2,1]
输出：0

示例 3：

1
2
输入：[3,2,3,4]
输出：10

示例 4：

1
2
输入：[3,6,2,3]
输出：8

思路：反向排序，第一个满足A[i+2] + A[i+1] > A[i]为所求

代码

1
2
3
4
5
6
7
8
def largestPerimeter(A):
    if len(A) <= 2:
        return 0
    A.sort(reverse = True)
    for i in range(len(A)-2):
        if A[i+2] + A[i+1] > A[i]:
            return A[i+2] + A[i+1] + A[i]
    return 0

题目四：242. 有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词。

示例 1:

1
2
输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

1
2
输入: s = "rat", t = "car"
输出: false

说明:
你可以假设字符串只包含小写字母。

进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

思路一：排序，比较s和t

代码一

1
2
3
4
5
6
7
8
9
def isAnagram(s,t):
    if len(s)!=len(t):
        return False
    s.sort()
    t.sort()
    for i in range(len(s)):
        if s[i] != t[i]:
            return False
    return True

思路二：字典

代码二：

1
2
3
4
5
6
7
8
9
from collections import Counter
def isAnagram(s,t):
    if len(s) !=len(t):
        return False
    else:
        if Counter(s) == Counter(t):
            return True
        else:
            return False