0

让我们假设我有一个类似这样的 circulatList

circularList = [12, 62, 76, 92, 3, 7, 12, 19].

从上面的列表中获得最小数字的最有效方法是什么。

4

6 回答 6

3

在列表中移动，记住并比较第一项，记住迄今为止最小的数字，并在我们回到列表的开头时返回它

在这里你可以看到它是如何完成的。

int findMinimum(Node* start) 
{ 
    int min = start -> data; 
    Node* t = start -> link; 
    while(t != start) 
    { 
        if(t -> data < min) 
            min = t -> data; 
        t = t -> link; 
    } 
    return min; 
}
于 2013-08-14T06:54:00.287 回答
3

根据您存储这些元素的数据结构的类型，您可以：

1）遍历列表并将每个值与当前最小值进行比较：

int compareValue = Integer.MAX_VALUE;
for(int value: circularList){
    if(value < compareValue);
        compareValue = value;
}

2) 如果数据类型实现 Collections.sort ，则对列表进行排序，并仅提取最小值。

Collections.sort(circularList);
于 2013-08-14T06:58:40.377 回答
2

除了@No Idea For Name：Collections.min(yourCollection)

于 2013-08-14T06:55:46.840 回答
2

在我回答之前我必须说：

首先，你说的和你的例子不匹配。[12, 62, 76, 92, 3, 7]是循环排序数组。但是你的例子：

[12, 62, 76, 92, 3, 7, 12, 19]

不是循环，这只是two sorted arrays.

其次，如果您谈论抽象的方法。您需要修改一些搜索算法方法。该方法的效率取决于您的情况。因此该算法将具有最坏情况、最佳情况和平均情况的性能。所以你所说的“最有效的方式”是你需要用你自己的测试用例来尝试的东西。

然后我的回答是，如果您需要从两个排序数组的组合中获得最小数字，我有比粗体比较更有效的方法：

int a;
int b = 0;\\your minimum possible value
//l= your array
for(int i=1; i<l.size;i++){
  b=l[i-1];
  a=l[i];
  if(b>a) // find the break point of the two sorted arrays
    if(a<l[0])
      return a;
    else 
      return l[0];
}
return l[0]; // in case the array already sorted(break point in 0 and l.size)

这样，当他们找到数组的断点时，您的循环将停止，并通过将第一个数字（12）与第二个数组的第一个数字（3）进行比较来返回最小的数字。

于 2013-08-14T08:15:15.753 回答
1

基本上只有一种算法可以从任意列表中获取最小元素：

  smallest = unset
  for each element in list:
      if smallest is unset OR element less than smallest:
          smallest = element

这如何映射到代码取决于特定的列表数据结构，甚至特定的编程语言可能会有所不同。但是基本结构是一样的，没有特别有效的方法。（复杂性在于列表长度O(N)在哪里。）N

您可以改进这一点的唯一方法是限制列表。例如，如果列表已经按照最小的优先排序，那么获取最小元素只是获取第一个元素的问题。

（但是对列表进行排序的成本将至少是O(N)......并且可能是O(NlogN)。排序以获得最小值将比仅迭代和测试效率低，如上所述。）

于 2013-08-14T07:11:16.517 回答
0

通用列表的单线程解决方案是：

int minValue= Integer.MAX_VALUE ;
for(int e: circularList )
    if( e < minValue ) minValue= e ;

对于第一个元素的位置已知的基于数组的排序循环列表：

minValue= circularList[firstElement] ;

对于一个基于数组的排序循环列表，其中最后一个元素的位置是已知的：

if( lastElement+1 >= circularList.length )
    minValue= circularList[0] ;
else
    minValue= circularList[lastElement+1] ;

对于第一个和最后一个元素的位置未知的基于数组的排序循环列表：

int minValue= Integer.MAX_VALUE ;
int prevValue= Integer.MIN_VALUE ;
for(int e: circularList ) {
    if( e < minValue )
        minValue= e ;
    if( e < prevValue ) {
        break;
    }
    prevValue= e ;
}

通用列表的多处理器友好解决方案是：

int threadCount= 8 ;
int nextStart= 0 ;
MinimumFindingThread[] threads= MinimumFindingThread[threadCount] ;
while( threadCount > 0 ) {
    count= ( circularList.size() - nextStart ) / threadCount ;
    threads[threadCount-1]= new MinimumFindingThread(circularList,nextStart,nextStart+count) ;
    threads[threadCount-1].start();
    nextStart= nextStart+count ;
    threadCount--;
}
int threadCount= 8 ;
int minValue= Integer.MAX_VALUE ;
while( threadCount > 0 ) {
    threads[threadCount-1].join();
    theadMin= threads[threadCount-1].getResult() ;
    if( theadMin < minValue ) minValue= theadMin ;
    threadCount--;
}
class MinimumFindingThread extends Thread {
    int[] list;
    int from;
    int to;
    int minValue;
    public MinimumFindingThread(int[] list,int from,int to) {
        this.list= list ;
        this.from= from ;
        this.to= this.to ;
    }
    public void run() {
        int minValue= Integer.MAX_VALUE ;
        for(int e: this.list[this.from:this.to] )
            if( e < minValue ) minValue= e ;
        this.minValue= minValue ; ;
    }
    public int getResult() {
        return this.minValue ;
    }
}
于 2013-08-14T06:55:55.050 回答