书架排书 逆序对

本文主要是介绍书架排书 逆序对，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

PayPal的一道笔试题，一个数组每一行代表书架上书的编号，每一行数组都有一个逆序对，想从逆序对小的开始排每一行的书，输入行数N，列数k, 以及N*k的数组;输出一个数组

比如输入

输出

 

 计算数组逆序对的函数是剑指offer上的，写出来不难，关键是怎么按照逆序对的大小把对应数组的顺序变换过来

数组直接输出有一个简单方法 Arrays.deepToString(num);

import java.util.*;
class Main{public static void main(String[] args){Scanner sc = new Scanner(System.in);while(sc.hasNext()){int N = sc.nextInt();int k = sc.nextInt();int[][] nums = new int[N][k];int[][] copy = new int[N][k];for(int i = 0; i < N; i++){for(int j = 0; j < k; j++){nums[i][j] = sc.nextInt();copy[i][j] = nums[i][j];}}Map<Integer,Integer> map = new HashMap<>();for(int i = 0; i < copy.length; i++){map.put(i,reversePairs(copy[i]));}List<Map.Entry<Integer,Integer>> list = new ArrayList<>(map.entrySet());Collections.sort(list,(a,b)->(a.getValue()-b.getValue()));Iterator<Map.Entry<Integer,Integer>> it = list.iterator();int[][] result = new int[N][k];int i = 0;while(it.hasNext()){Map.Entry<Integer,Integer> en = it.next();for(int j = 0; j < k; j++)result[i][j] = nums[en.getKey()][j];i++;}System.out.println(Arrays.deepToString(result));}}public static int reversePairs(int[] nums) {if(nums == null || nums.length == 0)return 0;return merge(nums,0,nums.length-1);}public static int merge(int[] nums, int l, int r){if(l >= r)return 0;int mid = l + (r - l)/2;int res = merge(nums,l,mid)+merge(nums,mid+1,r);int i = l;int j = mid + 1;int[] temp = new int[r-l+1];int k = 0;while(i <= mid && j <= r){if(nums[i] <= nums[j])temp[k++] = nums[i++];else{temp[k++] = nums[j++];res += mid-i+1;}}while(i <= mid) temp[k++] = nums[i++];while(j <= r)temp[k++] = nums[j++];i = l;for(int t: temp) nums[i++] = t;return res;}
}

 

这篇关于书架排书 逆序对的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---