首页 > 试题广场 >

特殊交换

[编程题]特殊交换

热度指数：1550 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

现有一个n个整数的序列，你要做的就是交换两个数的位置直到整个序列按照升序排列，那么将这个整数序列排好序，需要交换多少次？例如，1，2，3，5，4，我们只需要交换一次，即将5和4交换即可。

输入描述:

第一行输入一个正整数n（n≤1000），表示数字序列的元素个数，占一行；接下来一行输入从1到n的n个整数排序，中间用空格隔开

输出描述:

输出序列升序排列需要的最少交换次数

示例1

输入

4<br/>4 3 2 1

输出

算法知识视频讲解

查看答案及解析

好学上进

冒泡排序的变相考察。需要说明的是，题目出得不够严谨，应将“交换两个数的位置”明确为“交换相邻两个数的位置”。下面给出代码：

#include <iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int main(void)
{
    int n;
    while (cin>>n)
    {
        int* arr = new int[n];
        for (int i = 0; i < n; i++)
        {
            cin >> arr[i];
        }
        int count = 0;
        bool flag = true;
        for (int i = n-1; i >0; --i)
        {
            if (flag==false)
            {              
                break;
            }
            flag = false;
            for (int j = 0; j < i; j++)
            {
                if (arr[j]>arr[j+1])
                {
                    std::swap(arr[j], arr[j + 1]);
                    ++count;
                    flag = true;
                }
            }
        }
        cout << count << endl;
        delete[] arr;
    }
    return 0;
}

发表于 2016-04-21 21:46:09 回复(2)

良哥

  importjava.util.Scanner; 
  publicclassMain{ 

      publicstaticvoidmain(String[] args){ 
          Scanner sc
  =newScanner(System.in); 
          intN = sc.nextInt(); 
          int[] a =newint[N]; 
          for(inti=0;i<N;i++){ 
              a[i]= sc.nextInt(); 
          } 
          intcount =0; 
          inttemp =0; 
          for(inti
  =0;i<N-1;i++){ 

              for(intj=0;j<N-1-i;j++){ 

                  if(a[j+1]<a[j]){ 
                      temp=
  a[j]; 

                      a[j]=a[j+1]; 

                      a[j+1]=temp; 
                      count++; 
                  } 
              } 
          } 

          System.out.println(count); 
      } 
  } 

  就是冒泡交换的次数，每次把最大的值放在最后；题目意思应该是每次只能相邻的交换，所以冒泡交换的次数就是最后的结果 

  

发表于 2016-04-24 17:08:35 回复(1)

七月牧夫

#include<iostream>
using namespace std;
 
int main()
{
    int num;
    while (cin >> num){
        int a[1000],tem,total=0;
        for (int i = 0; i < num; i++) cin >> a[i];
        int *p = a;
        for (int i = 0; i < num; i++){
            for (int j = 0; j<(num-1); j++){
                if (*p>*(p + 1)){
                    tem = *p;
                    *p = *(p + 1);
                    *(p + 1) = tem;
                    total++;
                }
                p++;
            }
            p = a;
        }
        cout << total << endl;
   }
    return 0;
}//恢复有序状态，统计交换次数

发表于 2016-08-28 21:17:05 回复(0)

夏雨天

  #include <iostream> 

  #include <vector> 

  using namespace std; 

  classSolution 

  { 

  public: 

      intMinChange(vector<int>& array,intlen) 

      { 

          if(len<1) 

          { 

              return0; 

          } 

          intcount = 0; 

          for(inti = 0; i < len;i++) 

          { 

              for(intj = i + 1; j < len;j++) 

              { 

                  if(array[i]>array[j]) 

                  { 

                      count++; 

                  } 

              } 

          } 

          returncount; 

      } 

  }; 

  intmain() 

  { 

      intn = 0; 

      cin >> n; 

      vector<int>array; 

      inttemp = 0; 

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

      { 

          cin >> temp; 

          array.push_back(temp); 

      } 

      Solution s; 

      cout << s.MinChange(array,n); 

      return0; 

  }

发表于 2016-04-09 20:32:41 回复(0)

牛客554471号

按照例子看，是相邻两数交换（求逆序对），但与题意不符

发表于 2016-04-12 21:19:49 回复(1)

Spring100

本质上就是就逆序数对，三种解法：1）冒泡排序-适合数据小；2）归并解法；3）树状数组。

发表于 2017-08-18 09:50:17 回复(0)

IT工作

那个最后的求次数，如果是按照冒泡排序的话，结果就是6次。到底是按照怎样的方式来进行。？

发表于 2016-04-10 20:04:04 回复(1)

JonTang

importjava.util.*;

publicclassMain{

publicstaticvoidmain(String[] args){

Scanner sc=newScanner(System.in);

intn=sc.nextInt();

inta[]=newint[n];

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

a[i]=sc.nextInt();

}

intsum=0;

for(inti=0;i<n-1;i++){

for(intj=0;j<n-i-1;j++){

if(a[j]>a[j+1]){

inttemp=a[j];

a[j]=a[j+1];

a[j+1]=temp;

sum++;

}

System.out.println(sum);

}

发表于 2018-09-09 21:29:51 回复(0)

OYxx

function paixu(d,a){
    var b = a.replace(/\s+/g,"");
    var c = b.split("");
    var len = b.length;
    var count = 0;
    for(var i = 0;i<len-1;i++){
        for(var j = i+1;j<len;j++){
            var temp = c[i];
            if(temp>c[j]){
                var index = c[j];
                c[j] = temp;
                c[i] = index;
                count+=1;
            }
        }
    }
    alert(count);
}
var a = "4 3 2 1";
var aa = a .replace(/\s+/g,"");
var d = aa.length;
        paixu(d,a)

发表于 2017-09-23 11:42:33 回复(1)

xingfei_happy

/**

Created by wxf on 2017/8/4.
*/
var readline = require('readline');
const rl = readline.createInterface({
input:process.stdin,
output:process.stdout
});
var inputarr = [];
rl.on("line",function(input){
inputarr.push(input);
var n = +inputarr[0];
if(inputarr[1]){

 var newarr = inputarr[1].trim().split(" ");
 if(newarr.length == n) {

     var line = newarr.slice(0);
     var temp = 0, count = 0;
     console.log(line.length)

     for(var i = 0;i<line.length;i++){
         for(var j=  0;j<line.length-1-i;j++){
             if(line[j] > line[j+1]){
                 temp = line[j];
                 line[j] = line[j+1];
                 line[j+1] = temp;
                 count++;
             }
         }
     }
     console.log(count);
 }

}
})

求解，冒泡是这么冒的吗

编辑于 2017-08-04 12:40:44 回复(0)

Jimmy_gg

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

int main() {
    using namespace std;
    int n;
    while (cin >> n) {
        vector<int> arr(n);
        for (int i = 0; i < n; i++) {
            cin >> arr[i];
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (arr[i] > arr[j]) {
                    swap(arr[i], arr[j]);
                    ans++;
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

发表于 2017-07-10 09:43:08 回复(0)

牛客19951018

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        while(input.hasNext()){
            int number=input.nextInt();
            int[] a=new int[number];
            for(int i=0;i<number;i++){
                a[i]=input.nextInt();
            }
            int count=0;
            for(int i=1;i<number;i++){
                for(int j=0;j<i;j++){
                    if(a[j]>a[i]){
                        count++;
                    }
                }
            }
            System.out.println(count);
        }
        input.close();
    }

}

编辑于 2017-04-03 16:42:41 回复(0)

C/C++

ouge

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int n;
    int count = 0;
    cin >> n;
    vector<int> arr(n, 0);
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
        for (int j = 0; j < i; j++)
        {
            if (arr[j] > arr[i])
            {
                swap(arr[j], arr[i]);
        		count++;
            }
        }
    }
    cout << count;
    return 0;
}

发表于 2017-02-08 15:33:34 回复(0)

暮光

#include<bits/stdc++.h>
using namespace std;
#define ll long long
// 说白了，求逆序数，数据小，直接怼
int num[1010];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(int i=0;i<n;i++) scanf("%d",&num[i]);
        int ans=0;
        for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)
                if(num[i]>num[j]) ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}

发表于 2016-10-24 00:26:19 回复(0)

老码

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int n = in.nextInt();
            int[] array = new int[n];
            for (int i = 0; i < n; i++) {
                array[i] = in.nextInt();
            }
            int res = count(array);
            System.out.println(res);
        }
    }
    
    private static int count(int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        int res = 0;
        for (int i = 0; i < array.length; i++) {
            boolean flag = false;
            int j;
            for (j = i - 1; j >= 0;) {
                if (array[j] <= array[j + 1]) {
                    break;
                } else {
                  	res++;
                    swap(array, j, j + 1);
                    flag = true;
                    j--;
                }
            }
        }
        
        return res;
    }
    
    private static void swap(int[] array, int left, int right) {
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }
}

开始用的插入排序，发现过不了，只好改了改。

发表于 2016-09-22 18:48:37 回复(0)

testestest

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int bubbleSort(vector<int> A)
{
    int num=0;
    int n=A.size()-1;
    for(int i=n;i>0;--i)
    {
        for(int j=1;j<=i;++j)
        {
                if(A[j]<A[j-1])
                {
                    swap(A[j],A[j-1]);
                    num++;
                }
        }
    }
    return num;
}
int main()
{
    int num;
    cin>>num;
    vector<int> A;
    while(num--)
    {
        int tmp;
        cin>>tmp;
        A.push_back(tmp);
    }
    num=bubbleSort(A);
    cout<<num;
}

编辑于 2016-09-17 11:34:09 回复(0)

cc98

这道题不是求逆序对么？

发表于 2016-09-05 10:42:55 回复(0)

不吃草的兔子

  importjava.util.Scanner; 

  publicclassMain { 

      publicstaticintcount=0; 

      publicstaticvoidmain(String args[]){ 

          Scanner sc = newScanner(System.in); 

          int n = sc.nextInt(); 

          int[] data = newint[n]; 

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

              data[i] = sc.nextInt(); 

          } 

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

              for(intj=i;j<n;j++) 

                  if(data[i]>data[j]) 

                      count++; 

          System.out.println(count); 

          sc.close(); 

      } 
  }

发表于 2016-08-29 17:03:41 回复(0)

此番风景


	def bubble_count(lst, n):



	    """题意应该是只能交换相邻数字，冒泡排序是一种交换排序，统计交换次数即可"""



	    swap_count = 0



	    for i in range(n):       



	        for j in range(1,n-i):



	            if lst[j-1] > lst[j]:



	                lst[j-1], lst[j] = lst[j], lst[j-1]



	                swap_count += 1



	    return swap_count



	 



	 



	importsys



	 



	try:



	    whileTrue:



	        line = sys.stdin.readline().strip()



	        if not line:



	            break          



	        n = int(line)



	        nums = map(int, sys.stdin.readline().strip().split())



	        print bubble_count(nums, n)



	except:



	    pass

编辑于 2016-08-25 16:19:29 回复(0)

SevenRoar


	
	
		
		
			
			
				
				
					
					
						
						
							
							
								#include <iostream>
							

							
								#include <vector>
							

							
								#include <algorithm>
							

							
								using namespace std;
							

							
								 
							

							
								intmain()
							

							
								{
							

							
								    intn;
							

							
								    cin >> n;
							

							
								    vector<int> data(n);
							

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

							
								        cin >> data[i];
							

							
								    vector<int> tmp(data.begin(), data.end());
							

							
								    sort(tmp.begin(), tmp.end());
							

							
								    intswapt = 0;
							

							
								    intset = 0;
							

							
								    while(set < n)
							

							
								    {
							

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

							
								        {
							

							
								            vector<int>::iterator it = find(data.begin(), data.end(), tmp[i]);
							

							
								            intpos = it - data.begin();
							

							
								            for(intj=pos; j>i; j--)
							

							
								            {
							

							
								                swap(data[j], data[j-1]);
							

							
								                swapt ++;
							

							
								            }
							

							
								            set ++;
							

							
								        }
							

							
								    }
							

							
								    cout << swapt << endl;
							

							
								    return0;
							

							
								}