1

我写了一个方法来在不使用排序的情况下找到数组中第二小的数字。我想我可以扩展相同的逻辑来找到数组中的第三小数字..但是我意识到这并不容易..我的大脑一定是糊涂了由于缺乏睡眠或其他原因。下面是我的 findSecondSmallest 和 findThirdSmallest 代码。有人可以为以后纠正我的逻辑缺陷吗？

public class ArrayElementSelection{
    public static int findSecondSmallest(int[] a){
            int N = a.length;
            int min = 0;
            int secondSmallest = 0;
            for(int i=1;i<N;i++){
                if(a[i] < a[min]){
                    secondSmallest = min;
                    min = i;

                }else if(a[i] < a[secondSmallest]){
                    secondSmallest = i;
                }
            }
            return a[secondSmallest];
        }

    public static int findThirdSmallest(int[] a){
            int N = a.length;
            int min = 0;
            int secondSmallest = 0;
            int thirdSmallest = 0;
            for(int i=1;i<N;i++){
                if(a[i] < a[min]){
                    min = i;
                }else if(a[i] < a[secondSmallest]){
                    secondSmallest = i;
                }else if(a[i]< a[thirdSmallest]){
                    thirdSmallest = i;
                }
            }

            return a[thirdSmallest];
        }

    public static void main(String[] args) {
         int[] a = new int[]{4,2,3,1,5};
         System.out.println(findThirdSmallest(a));
    }
}

>> 4
4

9 回答 9

3

好吧，让我们清理一下。我们想找到数组中第三小的元素。

    NavigableSet<Integer> min3 = new TreeSet<Integer>();
    //We keep only 3 elements in min3, as soon as the set size grows over 3
    //we remove the last element, which is the max.

    for (int x : array) {
        min3.add(x);
        if (min3.size() > 3) {
            min3.pollLast();
        } 
    }

    if (array.length >= 3) {
        Integer thirdMinimum = min3.pollLast();
        System.out.println(thirdMimimum);
    } else {
       //array must contain at least 3 elements
    }

上面的代码片段找到了第三个唯一最小值。如果我们保留一个排序的整数列表，而不是一组整数。我们可以找到第三个非唯一最小值。

于 2013-07-11T18:06:04.373 回答
3

当您更新三个值之一时，您可能还需要更新其他值。

如果你有一个新的最小值，以前的最小值现在是第二低的......等等。

基于同样的推理，我怀疑您的第二低示例也不适用于所有数组。

在如下数组上运行您的示例（或手动运行逻辑，这更容易）：[5,4,3,2,1]

您最终会得到指向正确位置的最小值，而第二/第三仍然指向 0。当您找到要保留的新值时，您基本上需要“移动”上面的值。

于 2013-07-11T17:47:27.310 回答
2

这是在数组中查找 3 个最小项的逻辑。假设您的源数组有 100 个元素。创建一个名为 temp 的新数组，其中包含 3 个元素，并立即将源数组中的前 3 个元素添加到其中，然后对其进行排序（对 3 元素数组进行排序很简单）。记下 temp 中最大元素的大小，称为 maxTemp。

现在开始从第 4 个元素循环到整个源数组。如果你找到一个比 maxTemp 更小的元素：

1）确定这个新值在临时数组中的位置，然后将其放入并相应地向上移动较大的值。摆脱以前的 maxTemp ，因为它现在太大而无法获得资格。

2) 设置新的 maxTemp

3）继续循环

完成后，您将拥有包含 3 个最小元素的临时数组。

于 2013-07-11T17:50:18.293 回答
2

有一个通用的方法可以做到这一点：使用优先级队列。

  • 创建一个优先队列，其中最大的项目首先出队
  • 现在遍历列表中的项目，将它们添加到优先级队列中
  • 每当优先级队列超过 k 个项目时，出列一个项目
  • 完成迭代后，第 k 个最小的项目位于优先级队列的前面

优先队列操作需要O(log(X))时间，其中X是队列中的项目数。由于我们的优先级队列不超过k，因此每个操作都需要O(log(k))时间。整个过程需要O(n log(k))时间，O(n)如果你k通过设置k=3.

于 2013-07-11T20:40:41.177 回答
1

可能不是最好的方法，但为了扩展您的第一个示例的工作方式，我相信它看起来像这样：

public static int findThirdSmallest(int[] a){
        int N = a.length;
        int min = 0;
        int secondSmallest = 1;
        int thirdSmallest = 2;
        for(int i=1;i<N;i++){
            if(a[i] < a[min]){
                thirdSmallest = secondSmallest;
                secondSmallest = min;
                min = i;
            }
        }
        return a[thirdSmallest];
    }

如果数组长度小于 3，它将有错误，但否则我认为它应该可以工作。

编辑：实际上看你的算法是不正确的，我不相信有任何方法可以得到第 n 个最小的数字，而只通过数组 1 次，天真你需要通过找到最小值，然后再通过并与 min 比较以找到下一个数字，依此类推。我天真地说，因为这对于获得第 n 个最小元素的性能很差，但它可以完成工作。

于 2013-07-11T17:50:33.317 回答
1

让我们假设您是通过阵列的单程的一部分。到目前为止，你有最小的、第二小的和第三小的数字。

你看到的下一个数字可能是新的最小的、第二小的或第三小的，所以你的程序必须处理这个问题。

这是一个通常一次性完成的示例。您可以使用相同的方法通过简单地更改第一个参数来找到最小的、第二小的或第十小的。复杂度为 O(n*m) 其中 n 是数组的大小，m 是您想要获得的元素的顺序（例如，对于第三小，m 是 3）：

public class Smallest {

/**
 * Returns the index of the "pos"th smallest element.
 * 
 * @param pos
 *            Which element to return
 * @param a
 *            The array to search
 * @return -1 if there are less than pos elements
 */
public static int findSmallest(int pos, int[] a) {
    int i, j;

    // Keep an array of "pos" elements.
    List<Integer> smallest = new ArrayList<Integer>(3);

    // Init with -1 to indicate we haven't found an element yet.
    for (i = 0; i < pos; i++) smallest.add(i, -1);

    // Search for the smallest "pos" elements.
    for (i = 0; i < a.length; i++) {
        // See where in our smallest array, this element goes.
        for (j = 0; j < pos; j++) {
            Integer spos = smallest.get(j);
            if ((spos == -1) || (a[i] < a[spos])) {
                // The current element a[i] is the "j+1"th smallest.
                smallest.add(j, i);
                smallest.remove(3);
                break;
            } // if ((spos == -1) || (a[i] < a[spos]))
        } // for (j = 0; j < pos; j++)
    } // for (i = 0; i < a.length; i++) 
    return smallest.get(pos-1);
}

/**
 * @param args
 */
public static void main(String[] args) {
    // Find the 3rd smallest in the set.
    int a[] = {9,3,4,8,1,2,5,7,6};
    int thirdSmallest = findSmallest(3, a);
    System.out.println("Third smallest is a[" + thirdSmallest +"]="+a[thirdSmallest]);
}
}
于 2013-07-11T19:01:38.263 回答
0

我觉得这很有趣，所以我很快写了一个小的递归方法来解决它。这解决了给定的第 N 个最小元素（整数数组、第 N 个最小数字和 0（起始引用））

public class Thir {
    public static void main(String[] args) {
      int[] a = new int[]{4,2,3,1,5};
      System.out.println(findNthSmallest(a,3,0));
    }

    static int findNthSmallest(int [] array, int n, int last) {
      if (n == 0)
        return last;
      int MAX = 9999;
      int pos = 0;
      int curMin = 0;
      boolean changed = false;
      for (int i = 0; i < array.length; i++)
      {
        if (changed == false && array[i] > last)
         {
          curMin = array[i];
          changed = true;
         }
        if (array[i] < curMin)
        {
          pos = i;
          curMin = array[i];
        }
      }
      array[pos] = MAX;
      return findNthSmallest(array, n-1, curMin);
    }
}
于 2013-07-11T17:58:10.810 回答
0 
public int thirdSmallest(Int[] arr){

    for(int x = 0; x < arr.length; x++){
       for(int y = 0; y < arr.length; y++){
           if(arr[x] > arr[y]){
             int z = arr[x];
             arr[x] = arr[y];
             arr[y] = z;
           }
       }       
    }
  return arr[2]; //third smallest
}
于 2013-07-11T18:07:03.560 回答
0

您只需要使用一些优先级队列或 TreeSet 即可在 N * log N 时间内获得第 X 个最小或最大元素，否则您将在 N * M 时间内完成，这太糟糕了，无法考虑。

基本上在遍历数组时创建 TreeSet 并将项目放入其中，然后在完成后 - 您可以简单地迭代 TreeSet 并且迭代器下的第 N 个项目就是您要查找的内容。

于 2013-07-11T18:00:40.017 回答