我遵循一个好的方法吗？

  • Z时代
  • 2024-01-10
  • 分类：问答

请找到讨论问题的链接。我遵循一个好的方法吗？

Sorting | Amazon Interview Question

我跟着采取随机排列这下面的方法。希望你的建议可以遵循什么其他方法来解决问题： -

public class ThreeMachineInsertionSorting { 
    public static void main(String[] args) { 
     int[] ar1 = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1,-10}; 
     int[] ar2 = { 20, 19, 18, 17, 16, 15, 14, 23, 12, 11, 10 }; 
     int[] ar3 = { 20, 19, 21, 122, 10, 9, 11, 12, 4, 13, 18, 17 }; 
     performInsertionSort(ar1, ar2, ar3); 
    } 
    private static void performInsertionSort(int[] ar1, int[] ar2, int[] ar3) { 
     int[][] arrayOfArrays = { ar1, ar2, ar3 }; 
     int [] unSortedArray= mergeArrays(ar1,ar2,ar3,arrayOfArrays); 
     int i,j,key; 
     for(i=1;i<unSortedArray.length;i++){ 
      key= unSortedArray[i]; 
      j=i-1; 
      while(j>=0 && key<unSortedArray[j]){ 
       unSortedArray[j+1] = unSortedArray[j]; 
       j--; 
      } 
      unSortedArray[j+1] = key; 
     } 
     System.out.println("Size of the unSorted array is :=" + unSortedArray.length); 
     shareLoad(unSortedArray, arrayOfArrays); 
    } 
    private static void shareLoad(int[] sortedArray, int[][] arrayOfArrays) { 
     int loadFactor = sortedArray.length/3; 
     int index=0; 
     while(index<sortedArray.length){ 
      for(int [] ar : arrayOfArrays){ 
       for(int i=0; i<ar.length;i++){ 
        if(i<=loadFactor){ 
         ar[i] = sortedArray[index]; 
         index++; 
        } 
       } 
      } 
     } 
     for(int [] ar : arrayOfArrays){ 
      System.out.println("******************************************array properties**************************************"); 
      System.out.println("Size of array::" + ar.length); 
      for(int i=0; i<ar.length;i++){ 
       System.out.print(ar[i]+" "); 
      } 
      System.out.println("\n******************************************************************"); 
     } 
    } 
    private static int[] mergeArrays(int[] ar1, int[] ar2, int[] ar3,int[][] arrayOfArrays) { 
     int[] colaboratedArray = new int[ar1.length + ar2.length + ar3.length]; 
     System.out.println("Length of multi-dimensional array :-" 
       + arrayOfArrays.length); 
     int i = 0; 
     while (i < colaboratedArray.length) { 
      for (int[] ar : arrayOfArrays) { 
       for (int j = 0; j < ar.length; j++) { 
        colaboratedArray[i++] = ar[j]; 
       } 
      } 
     } 
     return colaboratedArray; 
    } 
}

回答：

这里有点幼稚的解决方案。

使用就地排序算法对M1，M2和M3进行排序。

通过找出M1中所有元素都可以换出M3中较小元素的点来组合M1和M3。

为了找到这个点，在M3中取1/9的数字并移到M1中的缓冲区。请注意，1/9的数字恰好是可用的10％容量。我们从M3中最小的桶开始，并将其与M1中最大的桶进行比较。通过比较M3桶的最大值和M1桶的最小值，我们可以确定是否可以将它们完全换出。如果我们可以将水桶从M1移到M3并从M3中抽入新水桶。这样做，直到我们有M1和M3分区。

现在我们必须再次分类M1和M3。现在我们必须从M2中取出最小的元素，并将它们移动到M1，直到我们划分出M1和M2。完成之后，我们可以对M1和M2进行排序。请注意，M1现已完成。

通过对M2和M3进行分区然后对两者进行排序并解决问题。

请注意，该解决方案要求我们对所有机器进行三次分类，并且每个数据元素在最坏情况下在机器之间移动了3次。

如果我们能够找到两个未排序集合的中位数，那么我们可以根据这个中位数然后转移元素来划分这些集合，并且只有在我们知道最终数字已经打开每台机器。

如果我们能够在不传输数据的情况下高效地找到3个未分类集的第K个最大元素，可以进一步改进。

以上是 我遵循一个好的方法吗？ 的全部内容， 来源链接： utcz.com/qa/261431.html

回到顶部