序列交换

 

	
	

		//先判断长度，如果长度为2的话，直接返回1。接着初始化sum为0；
	

	

		//然后再判断获取到的数组中是否有重复的值，如果有重复的值就把sum加1，然后结束判断。
	

	

		//最后借助二层循环，判断数组中的任意两个值，如果不同就把sum加1。
	




	



	var readline = require('readline');



	var ri = readline.createInterface({



	     input: process.stdin,



	     output: process.stdout



	});



	var is_first_line = true;



	ri.on('line',function(line){



	     if(is_first_line){



	       var n = parseInt(line);



	       is_first_line = false;



	       return



	     }



	     var arr=line.split(" ");



	     if(arr.length === 2) {



	       console.log("1");



	       return;



	     }



	      



	     var ary=arr.sort();



	     var sum = 0;



	     for(var i=0;i<ary.length;i++){



	         if(ary[i]==ary[i+1]){



	             sum++;



	             break;



	         }



	     }



	     for(var i=0;i<arr.length;i++){



	         for(var j=i+1;j<arr.length;j++){



	             if(arr[i] !== arr[j]){



	                 sum++;



	             }



	         }



	     }



	     console.log(sum);



	})

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>

int main() {
    using namespace std;
    int n;
    while (cin >> n) {
        vector<int> arr(n);
        set<vector<int> > arrset;
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                vector<int> temp(arr);
                swap(temp[i], temp[j]);
                arrset.insert(temp);
            }
        }
        cout << arrset.size() << endl;
    }
    return 0;
}

#include <iostream>
using namespace std;
//统计每个数字出现的次数
//如果每个数字仅出现一次，能得到不同的序列的数量就是每个数字出现次数两两相乘之和
//如果有数字出现两次或以上，能得到不同的序列的数量就是每个数字出现次数两两相乘之和再加一
int main(){
	int n,a[51],num[51]={0};
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		num[a[i]]++;
	}
	int flag=0,res=0;
	for(int i=1;i<=50;i++)
		if(num[i]>=2)
			flag=1;
	for(int i=1;i<50;i++){
		for(int j=i+1;j<51;j++){
			res+=(num[i]*num[j]);
		}
	}
	res+=flag;
	cout<<res<<endl;
	return 0;
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.LinkedList;

public class Main {
    public static void swap(int[] arr, int a, int b) {
        int temo = arr[b];
        arr[b] = arr[a];
        arr[a] = temo;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        String string = "";
        while ((string = bufferedReader.readLine()) != null) {
            String[] strings = bufferedReader.readLine().split(" ");
            int[] ints = new int[strings.length];
            for (int i = 0; i < strings.length; i++) {
                Integer temp = Integer.parseInt(strings[i]);
                ints[i] = temp;
            }
            int res = getSequenceExchangeCount(ints);
            System.out.println(res);
        }
    }

    public static int getSequenceExchangeCount(int[] arr1) {
        int res = 0;
        int count = 0;
        boolean[] visited = new boolean[arr1.length];
        HashSet<LinkedList<Integer>> hashSet1 = new HashSet<>();
        HashSet<int[]> hashSet = new HashSet<>();
        HashSet<String> hashSet2 = new HashSet<>();
        for (int i = 0; i < arr1.length - 1; i++) {
            visited[i] = true;
            for (int j = i + 1; j < arr1.length; j++) {
                int[] arr = arr1.clone();
                if (arr[i] == arr[j]) {
                    count++;
                }
                LinkedList<Integer> linkedList = new LinkedList<>();
                swap(arr, i, j);
                int[] temp = new int[arr1.length];
                String string = new String();
                for (int k = 0; k < arr1.length; k++) {
                    linkedList.add(arr[k]);
                    temp[k] = arr[k];
                    string += arr[k];
                }
                hashSet1.add(linkedList);
                hashSet.add(temp);
                hashSet2.add(string);
                linkedList.clear();
                swap(arr, i, j);
            }
        }
      /*  System.out.println("0! " + hashSet.size());
        System.out.println("1! " + hashSet1.size());
        System.out.println("2! " + hashSet2.size());*/
        if (count != 0) {
            res = hashSet1.size() - count + 1;
        } else {
            res = hashSet1.size();
        }
        return res;
    }


}

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int inf = 0x3f3f3f3f;
const ll INF = (ll)inf*inf;
const int maxn = 55;
int main()
{
    set<vector<int> >st;
    int n;cin>>n;
    int val;
    vector<int>vt;
    for(int i=0;i<n;i++){
        scanf("%d",&val);
        vt.push_back(val);
    }
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            swap(vt[i],vt[j]);
            st.insert(vt);
            swap(vt[i],vt[j]);
        }
    }
    cout<<st.size()<<endl;
 
    return 0;
}

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
/*思路就是要注意比较吧，一开始我以为能凭借着set集合来去除重复值，但是，
如果没有重新开辟内存空间的话，指向同一个内存地址，这样子，就会存不进去，然后我想着
用数组的clone()方法，给他重新开辟了一个内存空间。但是问题又来了，相同的数，存的话，
会认为是不同的，因为什么呢？集合的contains()方法，调用的是Object的equals方法， 而 Object的equals比较的是对象是否相等。没办法这里只能自己写比较了，而且，就是自己写
也一定要记得每次都要先用clone复制个新的数组，再去变换序列，不然先变换序列在复制的话
，就会收到影响。这就是整体思路，与我走过的弯弯道道吧。
*/
public class Main{

    public static void main(String[] args) {
        // TODO Auto-generated method stub
          Scanner input = new Scanner(System.in);
          List<int[]> set = new ArrayList<int[]>();
          int len = input.nextInt();
          int[] arr = new int[len];
          for(int i = 0;i < len;i++){
              arr[i] = input.nextInt();
          }
          int temp1,temp2 ;
          
          for(int i =0;i<len;i++){
              for(int j = i+1;j<len;j++){
                  int[] arr_cop = arr.clone();
                  temp1 = arr_cop[i];
                  temp2 = arr_cop[j];
                  arr_cop[i] = arr_cop[j];
                  arr_cop[j] = temp1;
                  if(contains(set,arr_cop))
                      set.add(arr_cop);
                  
              }
          }
          System.out.println(set.size());
          input.close();
          
    }
    public static boolean contains(List<int[]> ls,int[] arr){
        for(int[] l : ls){
            for(int i = 0;i<l.length;i++){
                
                if(l[i] == arr[i]&&i==l.length-1){
                    return false;
                }else if(l[i] != arr[i]){
                    
                    break;
                }
            }
        }
        return true;
    }
    
    
    

}

两种方法：
方法一:利用set<vector<int>>将vector中的每两个元素交换后加入到set中,
最后set中的个数就是答案
方法二：先设置sum = 0，然后如果序列中有重复的则sum不累加，有重复则sum加1.
通过二重循环即可得到答案，但最后如果有重复sum应该再加一

import java.util.Scanner;
import java.util.ArrayList;

public class Main
{
    public static void main(String[] args)
    {
        Scanner sca = new Scanner(System.in);
        ArrayList Int = new ArrayList();
            int n = sca.nextInt();
            //coun1记录共多少次交换    coun记录重复次数  o排除第一次与本身相同
            int coun=0 ,coun1=0;
            int o=0;
            for (int i = 0; i < n; i++)
            {
                Int.add(sca.nextInt());
            }
            for(int i=0;i<n;i++)
            {
                for(int j=i+1;j<n;j++)
                {
                    coun1++;
                    if(Int.get(i)==Int.get(j))
                    {
                         if(o!=0)
                             coun++;
                         o=1;
                    }
                }
            }
    System.out.println(coun1-coun);
    }

}

import java.util.*;
 
public class Main{
public static void main(String [] args){
    Scanner scanner = new Scanner(System.in);
    //表示元素的个数
    int number = scanner.nextInt();
    int [] value = new int [number];
    int index = 0;
    while(index<number){
        value[index++] = scanner.nextInt();
    }
    int count = 0;
    //循环确定个数
    boolean flag = false;
    HashSet<Integer> temp1;
    HashSet<Integer> temp2 = new HashSet<Integer>();
     
    for(int i = 0;i<value.length;i++){
        temp1 = new HashSet<Integer>();
        for(int j = i+1;j<value.length;j++){
            if(flag&&(value[j]==value[i]))
                             continue;
            if((value[j]==value[i])&&(temp1.contains(value[j])))
                continue;
            if((value[j]==value[i])&&temp2.contains(value[i]))
                continue;
            //首次出现两元素相同
            if(value[j]==value[i])
                    flag = true;
            else
                    flag = false;
            temp1.add(value[j]);
            count++;
        }
         temp2.add(value[i]);
    }
    System.out.println(count);
}
}

import java.util.*;
public class quanguo44 {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
   Scanner sc=new Scanner(System.in);
   while(sc.hasNext()){
	   int num=sc.nextInt();   //表示序列长度;
	   int arr[]=new int[num];
	   int i=0;
	   int count=0;
	   int doubleCount=0;
	   while(i<num){
		  arr[i]=sc.nextInt();
		  i++;
	   }
	  for(int j=0;j<num-1;j++){
		  for(int k=j+1;k<num;k++){
			  if(arr[j]==arr[k]){
				  doubleCount=1;
			  }else{
				  count++;
			  }
		  }
	  }
	  System.out.println(count+doubleCount);
   }
   sc.close();
	}
	}
//重复最多算一种;

//找所有不同的元素，设置flag，如果数组中有相同的元素，flag=true，则返回mount + 1，如果没有
//返回mount
import java.util.Scanner;
public class Main{
    public static void main(String args[]){
        Scanner scan=new Scanner(System.in);
        int count=0;
        if(scan.hasNext())
            count=scan.nextInt();
        int val[]=new int[count];
        for(int i=0;i<count;i++)
            if(scan.hasNext())
                val[i]=scan.nextInt();
        int mount=0;
        boolean flag=false;
        for(int i=0;i<count-1;i++)
            for(int j=i+1;j<count;j++){
                if(val[i]==val[j])
                    flag=true;
                if(val[i]!=val[j])
                	mount++;
            }
        if(flag)
            System.out.println(mount+1);
        else
        	System.out.println(mount);
    }
}

	#include<iostream>



	#include<string.h>



	using namespace std;



	 



	intinc(intnum)    //统计num个不同数字可以得到的序列个数



	{



	    inttotal = 0;



	    if(num >= 2)



	    {



	        for(inti = 1;i < num; ++i)



	            total+=i;



	    }



	    returntotal;



	}



	 



	intmain(){



	    intn;



	    inta[50];



	    intcnt, sNum;



	    inti;



	    intflag[51]={0};



	    while(cin>>n)



	    {



	        memset(a,0,sizeof(a));



	        memset(flag,0,sizeof(flag));



	        for(i = 0; i < n; ++i)



	        {



	            cin>>a[i];



	            ++flag[a[i]];



	        }



	        cnt = 0;



	        sNum = inc(n);    //统计所有的



	        for(i = 1; i < 51; ++i)



	        {



	            if(flag[i] >= 2)



	            {



	                sNum -= inc(flag[i]);    //减去有多个相同数字带来的重复



	                ++sNum;    //校正上一行带来的偏差



	                ++cnt;    //重复数字的组数



	            }



	        }



	        if(cnt>0)



	            sNum = sNum -cnt + 1;    //再减去多组重复带来的重复



	        cout<< sNum <<endl;



	 



	    }



	    return0;



	}

var n=parseInt(readline());
var arr=readline().split(' ').map(item=>parseInt(item));
var set=new Set();
for(var i=0;i<n;i++){
    
    for(var j=i+1;j<n;j++){
        var tmpArr=arr.slice();
        var tmp=arr[i];
        tmpArr[i]=tmpArr[j];
        tmpArr[j]=tmp;
        set.add(tmpArr.join(' '))//很惭愧这个地方之前字符串内没写空格，结果一直90%，后来发现如果不写空格的话，4和44就会看成一样的 }
}
print(set.size)

include

int main()

{

int n,num=0,flag=0;

int str[50];

scanf("%d",&n);

for(int i=0;i<n;i++) 

    scanf("%d",&str[i]);

if(n==2)

    num=1;

else

{

    for(int i=0;i<n;++i)

    {

        for(int j=i+1;j<n;j++)

        if(str[i]==str[j])

        {

            num++;

             flag=1;

            break;

        }

        if(flag)

         break;

   }

    for(int i=0;i<n;i++)

        for(int j=i+1;j<n;j++)

            if(str[i]!=str[j])

                num++;

}

printf("%d",num);

}

def main():
    length = int(raw_input())
    list_str = raw_input().split(' ')
    list_dict = {}
    for i in range(0,length):
        if list_str[i] in list_dict:
            list_dict[list_str[i]]  += 1
        else:
            list_dict[list_str[i]] = 1
    repeat_cost = 0
    label = 0
    for item in list_dict:
        repeat = list_dict[item]
        if repeat>1:
            label = 1
            repeat_cost += (repeat-1)*repeat/2
    if label==0:
        result = (length-1)*length/2
    if label==1:
        result = (length-1)*length/2 - repeat_cost + 1

    print result
     
if  __name__ == '__main__':
    main()