1

我怎样才能找到数组中三个最低整数的位置？我试图扭转它，但是当我添加第三个数字时，一切都变得糟糕了：p 有没有人设法将这个数字拉下来并帮助我？:)

编辑：在不更改或排序原始数组的情况下这样做会很好。

public static int[] lowerThree(int[] a)   {            
    int n = a.length;     
    if (n < 2) throw      
      new java.util.NoSuchElementException("a.length(" + n + ") < 2!");

    int m = 0;      // position for biggest
    int nm = 1;     // position for second biggest
    if (a[1] > a[0]) { m = 1; nm = 0; }
    int biggest = a[m];                // biggest value
    int secondbiggest = a[nm];           // second biggest
    for (int i = 2; i < n; i++) {
      if (a[i] > secondbiggest) {
        if (a[i] > biggest)   {
          nm = m;
          secondbiggest = biggest;     
          m = i;
          biggest = a[m];             
        }
        else    {
          nm = i;
          secondbiggest = a[nm];         
        }
      }
    } // for
    return new int[] {m,nm};   
}

编辑：我在这里尝试了一些东西，但它仍然不起作用。我得到错误的输出+重复...

  public static int[] lowerthree(int[] a)    {
    int n= a.length;
    if(n < 3)
        throw new IllegalArgumentException("wrong");
    int m = 0;      
    int nm = 1;
    int nnm= 2;

    int smallest = a[m];                // 
    int secondsmallest = a[nm];           /
    int thirdsmallest= a[nnm];

    for(int i= 0; i< lengde; i++)   {
        if(a[i]< smallest)   {
            if(smalles< secondsmallest)  {
                if(secondsmallest< thirdsmallest)  {
                    nnm= nm;
                    thirdsmallest= secondsmallest;
                }
                nm= m;
                secondsmallest= smallest;
            }  
            m= i;
            smallest= a[m];
        }
        else if(a[i] < secondsmallest) {
            if(secondsmallest< thirdsmallest)  {
                    nnm= nm;
                    thirdsmallest= secondsmallest;
            }
            nm= i;
            secondsmallest= a[nm];
        }
        else if(a[i]< thirdsmallest)    {
            nnm= i;
            thirdsmallest= a[nnm];
        }
    }
    return new int[] {m, nm, nnm}; 
}
4

6 回答 6

3

获取顶部或底部 k 通常是通过部分排序完成的。有改变原始数组的版本和不改变的版本。

如果您只想要底部（完全）3 并且想要获得它们的位置，而不是值，那么您的解决方案可能是最合适的。这就是我将如何更改它以支持底部三个。（我没试过编译运行，可能有小错误但大体思路应该符合）

public static int[] lowerThree(int[] a)   {            
  if (a.length < 3) throw      
    new java.util.NoSuchElementException("...");

  int indexSmallest = 0;
  int index2ndSmallest = 0;
  int index3rdSmallest = 0;
  int smallest = Integer.MAX_VALUE;
  int sndSmallest = Integer.MAX_VALUE;
  int trdSmallest = Integer.MAX_VALUE;

  for (size_t i = 0; i < a.length; ++i) {
    if (a[i] < trdSmallest) {
      if (a[i] < sndSmallest) {
        if (a[i] < smallest) {
          trdSmallest = sndSmallest;
          index3rdSmallest = index2ndSmallest;
          sndSmallest = smallest;
          index2ndSmallest = indexSmallest; 
          smallest = a[i];
          indexSmallest = i;
          continue;
        }
        trdSmallest = sndSmallest;
        index3rdSmallest = index2ndSmallest;
        sndSmallest = a[i];
        index2ndSmallest = i;
        continue;
      }
      trdSmallest = a[i];
      index3rdSmallest = i;
    }
  }
  return new int[] {indexSmallest, index2ndSmallest, index3rdSmallest};
}
于 2013-09-16T21:48:50.617 回答
1

我会将最低元素存储在 LinkedList 中，因此它不固定在最低 3 个元素上。你怎么看？

public static int[] lowest(int[] arr, int n) {

    LinkedList<Integer> res = new LinkedList();
    for(int i = 0; i < arr.length; i++) {

        boolean added = false;
        //iterate over all elements in the which are of interest (n first)
        for(int j = 0; !added && j < n && j < res.size(); j++) {
            if(arr[i] < res.get(j)) {
                res.add(j, i); //the element is less than the element currently considered
                //one of the lowest n, so insert it
                added = true; //help me get out of the loop
            }
        }
        //Still room in the list, so let's append it
        if(!added && res.size() < n) {
            res.add(i);
        }
    }

    //copy first n indices to result array
    int[] r = new int[n];
    for(int i = 0; i < n && i < res.size(); i++) {
        r[i] = res.get(i);
    }

    return r;

}
于 2013-09-16T22:07:58.777 回答
1

这将具有三个最低的数字，需要添加一些测试用例..但这是想法

int[] arr = new int[3];
    arr[0] = list.get(0);

    if(list.get(1) <= arr[0]){
        int temp = arr[0];
        arr[0] = list.get(1);
        arr[1] = temp;
    }
    else{
        arr[1] = list.get(1);
    }

    if(list.get(2) < arr[1]){
        if(list.get(2) < arr[0]){
            arr[2] = arr[1];
            arr[1] = arr[0];
            arr[0] = list.get(2);
        }
        else{
            arr[2] = arr[1];
            arr[1] = list.get(2);
        }
    }else{
        arr[2] = list.get(2);
    }



    for(int integer = 3 ; integer < list.size() ; integer++){

        if(list.get(integer) < arr[0]){
            int temp = arr[0];
            arr[0] = list.get(integer);
            arr[2] = arr[1];
            arr[1] = temp;
        }
        else if(list.get(integer) < arr[1]){
            int temp = arr[1];
            arr[1] = list.get(integer);
            arr[2] = temp;
        }
        else if(list.get(integer) <= arr[2]){
            arr[2] = list.get(integer);
        }
    }
于 2013-09-16T21:28:45.103 回答
1

简而言之，您需要将每个新元素与您手头的三个元素中的最大值进行比较，并在需要时交换它们（如果交换，则必须重新计算三个元素中的最大值）。

我会使用 2 个大小为 3 的数组：

  arrValues = [aV1  aV2  aV3]    (reals)
  arrPointers = [aP1  aP2  aP3]  (integers)

和一个 64 位整数类型，称之为maxPointer.

我将概述算法逻辑，因为我不熟悉 Java：

  Set arrValues = array[0] array[1] array[2]  (three first elements of your array)
  Set arrPointers = [0 1 2]   (or [1  2  3] if your array starts from 1)

  Iterate over the remaining elements. In each loop:

      Compare the Element scanned in this iteration with arrValues[maxPointer]
      If Element <= arrValues[maxPointer], 
                    remove the maxPointer element, 
                    find the new max element and reset the maxPointer
      Else
          scan next element
      End If
  Loop

在终止时，arrPointers应该有三个最小元素的位置。我希望这有帮助？

于 2013-09-16T21:58:37.767 回答
0

有一种简单的方法可以找到数组中三个最小数字的位置

例子 ：

      int[] arr={3,5,1,2,9,7};
      int[] position=new int[arr.length];
      for(int i=0;i<arr.length;i++)
      {
         position[i]=i;
      }
      for(int i=0;i<arr.length;i++)
      {
        for(int j=i+1;j<arr.length;j++)
        {
          if(arr[i]>arr[j]){
          int temp=arr[i];
          arr[i]=arr[j];
          arr[j]=temp;

          int tem=position[i];
          position[i]=position[j];
          position[j]=tem;
          }
        }
      }
     System.out.println("Lowest numbers in ascending order");

     for(int i=0;i<arr.length;i++)
     {
       System.out.println(arr[i]);
     }

     System.out.println("And their previous positions ");

     for(int i=0;i<arr.length;i++)
     {
       System.out.println(position[i]);
     }

输出

在此处输入图像描述

于 2018-01-05T10:36:44.270 回答
-1

你可以在 3 次迭代中完成。

您需要两个额外的内存，一个用于位置，另一个用于值。

第一次迭代，您会将最小值保存在一个额外的内存中，并将其位置保存在第二个内存中。在迭代时，您将插槽中的每个值与您保留在内存中的值插槽进行比较，如果您正在访问的项目小于您在额外值插槽中的内容，则替换值以及位置。

在第一次迭代结束时，您将找到最小的元素及其对应的位置。

你对第二和第三小的做同样的事情。

于 2013-09-16T21:15:38.420 回答