算法-java、c#或delphi-在数组中搜索一个大于arraySize/2的数字.在没有额外内存的情况下一次性完成

这确实是可能的；这项任务被称为"主导元素"，用于面试和家庭作业。阅读下面的文章进行适当的分析；解决方案本身很简单，但并不容易：证明它确实做到了它承诺的事情并不是一件小事（当然，除非你知道答案）。

http://www.cse.iitk.ac.in/users/sbaswana/Courses/ESO211/problem.pdf

element x;
int count ← 0;
For(i = 0 to n − 1)
{
    if(count == 0) { x ← A[i]; count ++; }
    else if (A[i] == x) count ++;
    else count −−
}
Check if x is dominant element by scanning array A.

请注意，时间是O（n），但据我所知，不可能一次完成，除非你确定存在主导元素

至于额外的内存，您将需要计数器i的内存；x，要检查和返回的元素；以及count，即假想工作集的大小。这是O（1），对于这样的问题通常被认为是可以的。

Moore在他的网站上描述了这个问题的解决方案（这里有一个例子）。

编辑：以下是一些Java代码，演示了所描述的算法：

public class Majority 
{
    public static void main(String[] args)
    {
        int[]a = new int[]{4, 4, 3, 5, 5, 5, 5, 5, 5, 6};
        int count = 0;
        int candidateIndex = 0;
        for (int i = 0; i < a.length; i++)
        {
            if (count == 0)
            {
                candidateIndex = i;
                count++;
            }
            else
            {
                if (a[i] == a[candidateIndex])
                    count++;
                else
                    count--;
            }
        }
        System.out.println("Majority element: " + a[candidateIndex]);
    }
}

在获得candidateIndex之后，您可以再次遍历数组，以验证它确实发生了N/2次以上。