您的位置: 首页  >  文章  >  长度为n的数组乱序存放着0至n-1. 现在只能进行0与其他数的交换.将数组中的元素按对应位置放置使得a[i]=i

长度为n的数组乱序存放着0至n-1. 现在只能进行0与其他数的交换.将数组中的元素按对应位置放置使得a[i]=i

分类: 文章 • 2024-06-09 22:00:22

原文链接：http://blog.****.net/u014659656/article/details/45115573

Question：长度为n的数组乱序存放着0至n-1. 现在只能进行0与其他数的交换.将数组中的元素按对应位置放置使得a[i]=i;

        此题目中的数据很像一个哈希表，但是只能用和0交换的方式进行位置调整。目前只知道算法复杂度为o（n^2）空间复杂度为o（1）的方法。

         思路：

          从最大的元素值n-1开始，一次将元素放到正确的位置。由于只能和0交换，所以一次操作需要两次对换。1.将第i个元素中的值和0交换，使得a[i]=0;2.将当前最大值curMax(即i)和0交换，从而使得a[i]=curMax=i;3.i--，重复1和2，直到所有的元素对号入座

长度为n的数组乱序存放着0至n-1. 现在只能进行0与其他数的交换.将数组中的元素按对应位置放置使得a[i]=i

[java] view plain copy
  1. package Algorithms;  
  2.   
  3. import java.util.HashSet;  
  4. import java.util.Random;  
  5. import java.util.Set;  
  6.   
  7. public class Solution {  
  8.     public static void main(String args[]){  
  9.         int n= 8;  
  10.         int[] arr = new int[n];  
  11.         produce(arr,n);  
  12.         System.out.println("排序之前： ");  
  13.         print(arr);  
  14.         System.out.println("----------------------------------");  
  15.         sort(arr);  
  16.         System.out.println("----------------------------------");  
  17.         System.out.println("排序之后： ");  
  18.         print(arr);  
  19.     }  
  20.       
  21.     public static void print(int[] arr){  
  22.         for(int i=0;i<arr.length;i++){  
  23.             System.out.print(" " + arr[i] + "   ");  
  24.         }  
  25.         System.out.println();  
  26.         for(int i=0;i<arr.length;i++){  
  27.             System.out.print("[" + i + "]" + "  ");  
  28.         }  
  29.         System.out.println();  
  30.         System.out.println();  
  31.     }  
  32.       
  33.     public static void produce(int[] rawArray, int n){  
  34.         Random r = new Random();  
  35.         int rn,count=0;  
  36.         Set<Integer> arr = new HashSet<Integer>();  
  37.         for(;count<n;){       //这里应该是count<n而不是count<=n；如果用小于等于，那么就是死循环，因为当产生n个不重复的数后，所有的数都有了，就会一直continue  
  38.             rn = r.nextInt(n);  
  39.             if(arr.contains(rn)){  
  40.                 continue;  
  41.             }  
  42.             arr.add(rn);  
  43.             count ++;  
  44.             rawArray[count-1] = rn;  
  45.               
  46.             //System.out.print(rn + "   ");  
  47.         }  
  48.         //System.out.println();  
  49.     }  
  50.       
  51.   
  52.     /** 
  53.      * 调用方法swap_with_zero来对array进行排序 
  54.      */  
  55.      public static void sort(int[] array) {  
  56.          int len = array.length;  
  57.          if(len <= 1){  
  58.              return;  
  59.          }  
  60.          for(int i = len - 1; i > 0; --i){       //从最后一位开始，将最大的数放到最大位置上，然后依次找次大的放  
  61.              if(array[i] == i) continue;        //已经相等，则不交换,避免不必要的重复交换  
  62.              swap_with_zero(array, array[i]);  //现将0和最后一位交换，以便将第n最大值换到第n大位置上  
  63.              print(array);  
  64.              int curMax = array[i];  
  65.              for(int j = i; j >= 0; --j){       //找出第n大的数  
  66.                   if(array[j] > curMax){  
  67.                       curMax = array[j];  
  68.                   }  
  69.              }  
  70.              swap_with_zero(array, curMax); //将第n大的数和0互换，从而放到第n大的位置上  
  71.              print(array);  
  72.          }  
  73.      }  
  74.        
  75.      public static void swap_with_zero(int[] array, int number){  
  76.             int len = array.length;  
  77.             int zIndex = -1;  
  78.             int nIndex = -1;  
  79.             for(int i = 0; i < len; ++i){  
  80.                 if(array[i] == 0){  
  81.                     zIndex = i;  
  82.                 }  
  83.                 if(array[i] == number){  
  84.                     nIndex = i;  
  85.                 }  
  86.             }  
  87.             int temp = array[zIndex];  
  88.             array[zIndex] = array[nIndex];  
  89.             array[nIndex] = temp;  
  90.   
  91.         }  
  92. }  

相关推荐