Java 寻找最大数和最小数的位置,循环

发布网友 发布时间：2022-04-14 23:26

我来回答

共3个回答

懂视网 时间：2022-04-15 03:48

题目： 有很多无序的数，如何从中选取最大的k个数 题目解析： 之前在《程序员编程艺术》上已经遇到这样的题——最小的k个数。本质都一样。 这里再总结一下： 思路1：使用类快排的方法 选取S中一个元素作为枢纽元v，将集合S-{v}分割成S1和S2，就像快速排序那

题目：

有很多无序的数，如何从中选取最大的k个数

题目解析：

之前在《程序员编程艺术》上已经遇到这样的题——最小的k个数。本质都一样。

这里再总结一下：

思路1：使用类似快排的方法

选取S中一个元素作为枢纽元v，将集合S-{v}分割成S1和S2，就像快速排序那样

如果k <= |S1|，那么第k个最小元素必然在S1中。在这种情况下，返回QuickSelect(S1, k)。

如果k = 1 + |S1|，那么枢纽元素就是第k个最小元素，即找到，直接返回它。

否则，这第k个最小元素就在S2中，即S2中的第（k - |S1| - 1）个最小元素，我们递归调用并返回QuickSelect(S2, k - |S1| - 1)。

此算法的平均运行时间为O(n)。

简化版本（三个元素中选取中间值）

//QuickSelect 将第k小的元素放在 a[k-1] 
void QuickSelect( int a[], int k, int left, int right )
{
 int i, j;
 int pivot;

 if( left + cutoff <= right )
 {
 pivot = median3( a, left, right );
 //取三数中值作为枢纽元，可以很大程度上避免最坏情况
 i = left; j = right - 1;
 for( ; ; )
 {
  while( a[ ++i ] < pivot ){ }
  while( a[ --j ] > pivot ){ }
  if( i < j )
  swap( &a[ i ], &a[ j ] );
  else
  break;
 }
 //重置枢纽元
 swap( &a[ i ], &a[ right - 1 ] ); 

 if( k <= i )
  QuickSelect( a, k, left, i - 1 );
 else if( k > i + 1 )
  QuickSelect( a, k, i + 1, right );
 }
 else 
 InsertSort( a + left, right - left + 1 );
}

随机化版本：

// Random Partition
int RandomInRange(int min, int max)
{
 int random = rand() % (max - min + 1) + min;
 return random;
}

void Swap(int* num1, int* num2)
{
 int temp = *num1;
 *num1 = *num2;
 *num2 = temp;
}

int Partition(int data[], int length, int start, int end)
{
 if(data == NULL || length <= 0 || start < 0 || end >= length)
 throw new std::exception("Invalid Parameters");

 int index = RandomInRange(start, end);
 Swap(&data[index], &data[end]);

 int small = start - 1;
 for(index = start; index < end; ++ index)
 {
 if(data[index] < data[end])
 {
  ++ small;
  if(small != index)
  Swap(&data[index], &data[small]);
 }
 }

 ++ small;
 Swap(&data[small], &data[end]);

 return small;
}


int MoreThanHalfNum_Solution1(int* numbers, int length)
{
 if(CheckInvalidArray(numbers, length))
 return 0;
 
 int middle = length >> 1;
 int start = 0;
 int end = length - 1;
 int index = Partition(numbers, length, start, end);
 while(index != middle)
 {
 if(index > middle)
 {
  end = index - 1;
  index = Partition(numbers, length, start, end);
 }
 else
 {
  start = index + 1;
  index = Partition(numbers, length, start, end);
 }
 }
 
 int result = numbers[middle];
 if(!CheckMoreThanHalf(numbers, length, result))
 result = 0;

 return result;
}

思路二：

堆排序的方法，只对前k个先排序，然后遍历整个序列。这样的方法特别适合大量的数据。

if(X > h[0]){
 h[0] = X;
 p = 0;
 while(p < K){
 q = 2*p + 1;
 if(q >= K)
  break;
 if((q < K-1) && (h[q+1] < h[q])) //这里必须q < K-1，才有后面的q+1
  q = q+1;
 if(h[q] < h[p]){
  t = h[p];
  h[p] = h[q];
  h[q] = t;
  p = q;
 }else
  break;
 }
}

思路三：

另外一种比较受限的方法：可以利用计数排序那样，当所有的N个数都为正数并且变化范围不大的时候，我们可以设置一个数组来统计每一个数据出现的次数。然后遍历这个数组，找到最大的k个数据即可。

for(sumcount = 0,v = MAXN - 1;v >= 0;v--){
 sumcount += count[v];
 if(sumcount >= k)
 break;
}
return v;

拓展：

毕竟对于大数据来说，我们要让认知面更广，往往处理大数据的方法，平时一般见不到。

对于不能保证所有的数为正数，且变换范围不大，我们也可以利用思路三来分组处理：

假设N个数中最大值max,最小值min。我们可以将[min,max]分成M个区域，每个小区域跨度为(max-min)/M，然后扫描一遍所有的数据，统计各个区域包含的数据。然后找到地k大数据出现在哪个区域范围内。然后再对该局域进行分块处理。

热心网友 时间：2022-04-15 00:56

Scanner s=new Scanner(System.in);
System.out.println("Input:");
String k=s.next();
String str="";
Scanner ss=new Scanner(System.in);
str=ss.nextLine();
String[] st=str.split(" ");
String os="";
for (int i = 0; i < st.length; i++) {
if (st[i].equals(k)) {
os+=i+1+" ";
}
}
System.out.println("Output:");
System.out.println(os);

热心网友 时间：2022-04-15 02:14

import java.util.Scanner;
public class FindMaxMin {
public static void main(String[] args) {

Scanner s = new Scanner(System.in);
int n = s.nextInt();
int max, maxIndex = 1, min, minIndex = 1;
int temp = s.nextInt();
max = min = temp;
for (int i = 1; i < n ; i++) {
temp = s.nextInt();
if (temp > max) {
max = temp;
maxIndex = i + 1;
}
if (temp < min) {
min = temp;
minIndex = i + 1;
}
}

System.out.println("OUTPUT : " + maxIndex + " " + minIndex) ;
}
}

这个是Java代码，可能写的不太好，但是能实现功能。