链家数组排序最小交换次数解法？

http://www.dewen.net.cn/q/7967 直接推公式

我怎么没这个题 你说的是去重排序的吗 如果是那个题 我用了TreeSet。。。

插入排序，统计次数

过了67%

直接放到set容器，100%。。 哈哈哈

treeset

最后怎么输出啊

//89%，不知道哪里有坑。。。 public static void main(String args[]){ Scanner cin = new Scanner(System.in); int n = cin.nextInt(); int[] array = new int[n]; int a = 0,b = 0,result = 0; for(int i = 0 ; i < n ; ++i){ array[i] = cin.nextInt(); if(array[i] == 1) a++; else if(array[i] == 2) b++; } for(int i = 0 ; i < a ; ++i){ if(array[i] != 1) result++; } for(int i = a ; i < a + b ; ++i){ if(array[i] == 3) result++; } System.out.println(result); }

一趟3路快排，稍微修改一下就行。

暴力做的，后来写完的，一开始只能过56，后来改了下，也不知道能不能过全部 public class Lianjia3 { private static boolean isTrue(int[] verify,int[] data, int n){ for (int i=0;i<n;++i){ if (verify[i]!=data[i]){ return false; } } return true; } private static void swap(int i,int j,int[] data){ int t=data[i]; data[i]=data[j]; data[j]=t; } private static int ans=Integer.MAX_VALUE; public static void solve(int index,int[] verify,int[] data,int n,int cur){ if (isTrue(verify, data, n)){ ans=Math.min(ans, cur); return; } if (verify[index]==data[index]){ solve(index+1, verify, data, n, cur); return; } int id=-1; for (int j=index+1;j<n;++j){ if(data[j]==verify[index] && verify[j]==data[index]){ id=j; break; } } if(id!=-1){ swap(index, id, data); solve(index+1, verify, data, n, cur+1); } if (id==-1){ for (int j=index+1;j<n;++j){ if(data[j]==verify[index] && verify[j]!=data[j]){ id=j; swap(index, j, data); solve(index+1, verify, data, n, cur+1); swap(index, j, data); } } } } public static void main(String[] args) { // TODO Auto-generated method stub Scanner in=new Scanner(System.in); int n=in.nextInt(); int[] data=new int[n]; int oneCount=0; int twoCount=0; int threeCount=0; for (int i=0;i<n;++i){ data[i]=in.nextInt(); if (data[i]==1){ oneCount++; }else if (data[i]==2){ twoCount++; }else{ threeCount++; } } int[] verify=new int[n]; int i=0; for (int j=0;j<oneCount;++j){ verify[i++]=1; } for (int j=0;j<twoCount;++j){ verify[i++]=2; } for (int j=0;j<threeCount;++j){ verify[i++]=3; } solve(0,verify, data, n, 0); System.out.println(ans); in.close(); } }

1中2和2中的1交换，1中的3和3中的1交换，2中的3和3中的2交换，每一次交换count+1; 剩下的就是1 2 3 互换的 ，每一次count+2

import java.util.Scanner; public class Solution { /** * @param args */ static int sum = 0; public static void main(String[] args) { // TODO Auto-generated method stub Scanner in = new Scanner(System.in); while (in.hasNext()) { int n = in.nextInt(); int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = in.nextInt(); } int lo = 0; int hi = n - 1; quick(arr, lo, hi); System.out.println(sum); } } public static void quick(int[] arr, int lo, int hi) { if (hi <= lo) { return; } int lt = lo; int i = lo + 1; int gt = hi; int tmp = arr[lo]; while (i <= gt) { if (arr[i] < tmp) { swap(arr, lt++, i++); } else if (arr[i] > tmp) { swap(arr, i, gt--); } else { i++; } } quick(arr, lo, lt - 1); quick(arr, gt + 1, hi); } public static void swap(int[] a, int i, int j) { if (a[i] != a[j]) sum++; int tmp = a[i]; a[i] = a[j]; a[j] = tmp; } } 三向切分快排，不知道好不好使

先一次遍历统计1的个数，2的个数和3的个数。然后统计本来应该是1的位置然而不是1的个数notone，本来应该是2的位置然而是3的个数cnt23，本来应该是3的位置是2的个数cnt32。结果为notone+max(can23，cnt32)。