2019.09.26算法课堂练习

1.按数值个数排序

描述

给定整数数组，请根据元素的频率对数组进行排序。 例如，如果输入数组是{2，3，2，4，5，12，12，2，3，3，3，12}，则将该数组修改为{3，3，3，3，2，2， 2，12，12，4，5}。 如果两个元素的频率相同，则以升序打印。

Solution

按出现频次排序，那么我们只需要统计每个数字出现的次数，以数字出现的次数为key进行排序，最后从头到尾输出排序后的数字个数。

时间复杂度 O(nlogn)

空间复杂度O(n)

Python

import collections
# 对数列按照出现频次排序
def frecuncySort(nums):
    count = collections.Counter(nums)
    # 以数字出现频次为key进行排序
    vals = [(-count[k], k) for k in count]
    vals.sort()
    # 出现次数从多到少，输出对应数字个数
    res = []
    for val, k in vals:
        res += [k] * (-val)
    return res

# IO输入输出
N = int(input())
for i in range(N):
    l = input()
    nums = list(map(int, input().split()))
    nums = map(str, frecuncySort(nums))
    out = ' '.join(nums)
    print(out)

Java

 public static List<Long> frecuncySort(List<Long> nums){
        // 计算频次，获取频次与数字对应的pairs
        Map<Long, Long> count = nums.stream().collect(Collectors.groupingBy(i -> i, Collectors.counting()));
        List<Pair> pairs = count.keySet().stream().map(key -> new Pair(key, count.get(key))).collect(Collectors.toList());

        // 按照频次对数字排序
        Collections.sort(pairs, (p1, p2) -> {
            // 频次相同按照数字大小排序
            if (p1.cnt == p2.cnt)
                return p1.value > p2.value ? 1:-1;
            return p1.cnt < p2.cnt ? 1:-1;
        });

        // 输出
        for(int i = 0; i < nums.size(); i++){
            nums.set(i, pairs.get(0).value);
            pairs.get(0).cnt--;
            if (pairs.get(0).cnt == 0)
                pairs.remove(0);
        }
        return nums;
    }

    public static class Pair{
        long value, cnt;

        Pair(long value, long cnt) {
            this.value = value;
            this.cnt = cnt;
        }
    }

2. 最小交换次数

描述

给定一个由N个不同的elements组成的数组，找到对数组进行排序所需的最小交换次数。您需要完成该函数，该函数返回一个表示对数组进行排序所需的最小交换次数的整数。

Solution

方法一：

遍历数组，判断当前元素是否在最终位置，否则把它交换到它的最终位置，（即每次交换至少让其中一个元素被放到其最终位置），统计总交换次数。

怎么判断当前元素是否在最终位置呢？

可以先对数组排序，得到每个数字对应最终位置的map。

python

def min_swaps(nums):
    # mp记录排序后数值应在的正确位置
    mp = {}
    sort_nums = sorted(nums)
    for i in range(len(sort_nums)):
        mp[sort_nums[i]] = i

    # 循环节个数
    lops = 0
    # 该位置的数是否被访问过
    flags = []
    for i in range(len(nums)):
        flags.append(False)
    for i in range(len(nums)):
        if not flags[i]:
            j = i
            while not flags[j]:
                flags[j] = True
                # j是当前值应在的正确位置
                j = mp[nums[j]]
            lops += 1
    return len(nums) - lops


case = int(input().strip())
while case:
    size = int(input().strip())
    nums = list(map(int, input().strip().split()))
    print(min_swaps(nums))
    case -= 1

java

public int minswap(List<Integer> nums){
    List<Integer> snums = new ArrayList<>();
    snums.addAll(nums);
    Collections.sort(snums);

    // 位置数组
    Map<Integer, Integer> inums = new HashMap<>();
    for (int i = 0; i<snums.size(); i++)
        inums.put(snums.get(i), i);

    int count = 0;
    for (int i = 0; i < nums.size(); i++){
        // 最终位置
        int target_i = inums.get(nums.get(i));
        while (target_i != i){
            int temp = nums.get(i);
            nums.set(i, nums.get(target_i));
            nums.set(target_i, temp);
            count++;
            target_i = inums.get(nums.get(i));
        }
        
    }
    return count;
}

方法二：

在原数组中，每个元素添加一个出边指向它最终的位置，这样画完出边后，最少会成一个环，最多n个环。 每一个环对应的交换次数等于元素数量-1，因此不需要交换的次数等于环数。交换次数 = n - 环数

python

def minswap(nums):
    # 排序
    snums = sorted(nums)
    # 位置数组
    inums = {snums[i]: i for i in range(len(snums))}
    count = 0
    visited = [False] * len(nums)
    # 计算环数
    for i in range(len(nums)):
        if visited[i]: continue
        j = i
        while not visited[j]:
            visited[j] = True
            j = inums[nums[j]]
        count += 1
    return len(nums) - count

3. 倒置个数

描述

有一个由N个实数构成的数组，如果一对元素A[i]和A[j]是倒序的，即i<j但是A[i]>A[j]则称它们是一个倒置，设计一个计算该数组中所有倒置数量的算法。要求算法复杂度为O(nlogn)

Solution

我们来回忆一下合并排序，合并排序的思路是首先对左半部分递归排序，再对右半部分递归排序，左右两部分有序后，合并这两部分，递归结束的条件是数组长度小于2，这时候不需要排序了。

合并的过程如下：

左半部分：L1 > L2 > L3 > L4

右半部分：R1 > R2 > R3 > R4 > R5

比较L1和R1的大小，如果L1 < R1, L1排为第一个，再比较R1和L2的大小….

在这个过程中，如果R1 < L1，那么R1与 L1…L4就组成了倒置对，因此我们可以在合并排序中统计这些倒置对。

python

def mergeSort(nums):
    if len(nums) < 2:
        return 0, nums
    count = 0
    mid = len(nums) // 2
    cl, l = mergeSort(nums[:mid])
    cr, r = mergeSort(nums[mid:])
    for i in range(len(nums)):
        if not r or l and l[0] < r[0]:
            nums[i] = l.pop(0)
        else:
            nums[i] = r.pop(0)
            count += len(l)
    return count + cl + cr, nums

def count(nums):
    return mergeSort(nums)[0]

4. 按照给定数组排序

描述

给定两个数组A1和A2，对A1进行排序，以使元素之间的相对顺序与A2中的相对顺序相同。 对于A2中不存在的元素。 最后按排序顺序附加它们。 还假定A2 中的元素数小于或等于A1 中的元素数，并且A2具有所有不同的元素。

Solution

统计A1数字出现的频次，遍历A2，按照统计频次输出对应数量的数，对于余下的数再排序后输出。

时间复杂度O(nlogn)

case = int(input().strip())
while case:
    size1, size2 = list(map(int, input().strip().split()))

    num1 = list(map(int, input().strip().split()))
    num2 = list(map(int, input().strip().split()))
    result = []
    for i in range(len(num2)):
        if num2[i] in num1:
            count = num1.count(num2[i])
            for j in range(0, count):
                print(num2[i], end=" ")
                num1.remove(num2[i])
    num1.sort()
    for i in range(len(num1)):
        if i == len(num1) -1:
            print(num1[i])
        else:
            print(num1[i], end= " ")
    case -= 1

java

public List<Long> mysort(List<Long> A1, List<Long> A2){
    Map<Long, Long> count = A1.stream().collect(Collectors.groupingBy(i -> i, Collectors.counting()));
    List<Long> res = A1.stream().filter(num -> !A2.contains(num)).collect(Collectors.toList());
    Collections.sort(res);
    int j = 0;
    for (Long num: A2){
        for (int i = 0; i<count.get(num); i++) {
            res.add(j, num);
            j += 1;
        }
    }
    return res;
}