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):
return [num * times for num, times in collections.Counter(nums).most_common()]
# 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 minswap(nums):
# 排序
snums = sorted(nums)
# 位置数组
inums = {snums[i]: i for i in range(len(snums))}
count = 0
for i in range(len(nums)):
target_i = inums[nums[i]]
while target_i != i:
nums[i], nums[target_i] = nums[target_i], nums[i]
count += 1
target_i = inums[nums[i]]
return count
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)
python
import collections
def mysort(A1, A2):
count = collections.Counter(A1)
res = []
for num in A2:
res += [num]*count[num]
del count[num]
for num in sorted(count):
res += [num]*count[num]
return res
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;
}
