余姚专业网站建设公司,行政部网站建设规划,湖南网站营销seo哪家好,深圳建设商城网站逆序对
题目
给定一个数组#xff0c;求其中有多少逆序对#xff0c;要求时间复杂度不超过nlogn。
思路
使用归并排序的分治思想#xff0c;将数组递归地分为左右两部分。在合并两个有序子数组时#xff0c;若左侧数组中的某个数大于右侧数组中的某个数#xff0c;则可…逆序对
题目
给定一个数组求其中有多少逆序对要求时间复杂度不超过nlogn。
思路
使用归并排序的分治思想将数组递归地分为左右两部分。在合并两个有序子数组时若左侧数组中的某个数大于右侧数组中的某个数则可以确定该左侧数组中的这个数和右侧数组中当前及其后的所有元素形成逆序对。递归合并的过程中统计所有逆序对的数量。
代码 private static int countInversions(int[] num) {int left 0, right num.length - 1;int[] temp new int[num.length];return countSum(num,temp,left,right);}private static int countSum(int[] num, int[] temp, int left, int right) {if(leftright){return 0;}int mid left (right - left) / 2;int count countSum(num,temp,left,mid);countcountcountSum(num,temp,mid1,right);countcountcountNum(num,temp,left,mid,right);return count;}private static int countNum(int[] num, int[] temp, int left, int mid,int right) {int ileft,jmid1;int k0,count0;while(imidjright){if(num[i]num[j]){temp[k]num[i];}else{temp[k]num[j];count count(mid-i1);}}while(imid){temp[k]num[i];}while(jright){temp[k]num[j];}for(int pleft;pright;p){num[p]temp[p];}return count;}
均衡
题目
这是一个通过移动数组元素值实现尽量“均衡”的问题。目标是使数组中元素尽量相等或者趋于相同的范围。每次只能移动 1 单位只能移动相邻的数组。
例如数组【146】下标为1的数组元素4可以移动移动一单位给1或者6将数组变为【236】或者【137】。
要求数组达到【344】,数组顺序不限。
思路
直接一个模拟
不断调整相邻的元素逐步趋近于配平。打印每次移动的过程直到达到平衡或接近平衡。
代码
public static void balanceArray(int[] arr) {int moves 0;int n arr.length;while (!isBalanced(arr)) {for (int i 0; i n - 1; i) {if (arr[i] arr[i 1]) {arr[i];arr[i 1]--;moves;printArray(arr, moves);}else if (arr[i] arr[i 1]) {arr[i]--;arr[i 1];moves;printArray(arr, moves);}}}System.out.println(Total moves: moves);}private static boolean isBalanced(int[] arr) {int total Arrays.stream(arr).sum();int remainder total % arr.length;int first arr[0];for (int i 1; i arr.length; i) {if (arr[i] ! firstMath.abs(first-arr[i])remainder) {return false;}}return true;}private static void printArray(int[] arr, int step) {System.out.println(Step step : Arrays.toString(arr));}
