来道题要求NlgN

给个数组
只能交换一次，任何不同位置的元素，形成一个permutation
问能形成不同的permutation的总个数
时间复杂度NlogN

给：2,3,4,5
2,3,4,5
3,2,4,5
2,4,3,5
2,3,5,4
5,3,4,2
......

我的太烂了
int res=1;
二维
   if([j]!=) res++;
return res;

int n = nums.length;
return 0.5 * ( n^2 - n);

感觉ON就行诶 大致写了下

1. class Solution {
   
2.     public int countPremutationWithOneSwap(int[] arr) {
   
3.         var map = new HashMap<Integer, Integer> ();
   
4.         int totalNum = arr.length, res = 0;
   
5.         for (int i = arr.length - 1; i > -1; --i) {
   
6.             map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
   
7.         }
   
8.         for (int i = 0; i < arr.length; ++i) {
   
9.             res += (totalNum - map.get(arr[i]));
   
10.             map.put(arr[i], map.get(arr[i]) - 1);
    
11.             totalNum--;
    
12.         }
    
13.         // no swap
    
14.         return res + 1;
    
15.     }
    
16. }

复制代码

O(n)即可，遍历数组，用一个map记录前面元素出现次数，对于每个元素a[i],count += i - map.get(a［i］)