6

我有一个包含 10 个整数值的数组。现在我想找出第二高的数字。我不应该使用任何 java API。这个问题是一位面试官问我的。他想要逻辑。他的要求是，我不应该遍历整个元素。有没有什么方法可以不用遍历就可以达到结果？遍历意味着遍历数组中的所有元素。想了很久，最后还是放弃了。如果有人能解释一下，那就太好了。我还问了关于排序的问题。他不希望对数组进行排序。

4

4 回答 4

10

不，这完全不可能。如果你不看所有的数据，你不可能知道第二高的值。

当然，您不必对所有数据进行排序，这可能是您的面试官的意思——但您确实需要至少查看每个元素一次。每个元素都有可能改变结果，因此需要检查。

于 2012-07-19T06:00:24.500 回答
1

如果您不至少查看每个元素一次，您将无法知道答案。但是，如果这不是您关心的问题，您可以使用二叉搜索树：

在计算机科学中，二叉搜索树 (BST)，有时也称为有序或排序二叉树，是一种基于节点的二叉树数据结构，具有以下特性：[1]

节点的左子树仅包含键小于节点键的节点。节点的右子树仅包含键大于或等于节点键的节点。左右子树也必须是二叉搜索树。
来源：http ://en.wikipedia.org/wiki/Binary_search_tree

你将如何找到第二大元素？

那么从BST是如何形成的，你知道最大的元素是最右边的元素（从根节点开始，取正确的孩子，直到你无处可去）。

现在，如何识别第二大？
好吧，这可能不是最有效的方法，但让我们在以下情况下对其进行分解：

  1. 最大节点是树根并且没有子节点 - 没有第二大元素，因为树中只有一个节点

  2. 最大节点是树根（没有右子节点） - 第二大元素是左子树中的最大元素

  3. 最大元素不是树根，但不是叶子（有左孩子） - 第二大元素是他的左孩子

  4. 最大的元素不是树根，而是叶子（没有孩子）-第二大元素是他的父母

我相信你现在可以弄清楚模式和一个简单的算法：D

于 2012-07-19T06:34:50.567 回答
1

我知道这已经得到回答，但我在想这样的事情。 

    double maxVal = array[0];
    for (int i=1; i < array.length; i++) {
        if (array[i] > maxVal) {
            maxVal = array[i];
        }
    }

从技术上讲，我不是遍历整个数组，而是遍历长度的 n-1，因为我将第一个值分配给最大值。我相信还有其他方法，但这似乎是关于面试官可能想要的。

于 2012-10-03T21:40:00.367 回答
0

逻辑是如此简单，我已经在一个 for 循环中实现了这一点。

我给你我的程序，如果你想要算法，我也可以给你。

公共静态无效主要（字符串[]参数）{

    int[] arr={0,12,74,56,2,63,45};
    int f1=1,f2=0,temp=0;
    int num=0;

    for(int i=0;i<arr.length;i++){
        num=arr[i];
        if(f1<num)
        {
            temp=f1;
            f1=num;
            num=temp;
        }
        if(f2<num)
        {
            temp=f2;
            f2=num;
            num=temp;
        }
    }
    System.out.println("First Highest "+f1+" Second Highest "+f2+" Third "+num);

}
于 2014-01-08T07:38:40.230 回答