用java查找最小k個元素

Ⅰ 找出第k個最小數

！修改成從鍵盤輸入的了，輸入數字的時候要每次輸入一個數後敲一下回車，因為用的是readLine方法

呵呵，我上學期演算法設計與分析的實驗
使用的是快速排序演算法，不需要對原數列進行排序便可求出第k個元素

實驗6 快速排序演算法求第K個元素
 問題描述
利用快速排序的方法，在不將所有數據排序的情況下找出數據中第K小元素。
 設計思想
利用快速排序的方法，將數列A[i..j]分成A[i..p],A[p+1..j]2部分，並使的A[i..p]中的每個元素的鍵值都不大於A[p+1..j]中的每個元素的鍵值，這樣如果k<=p,則第K個元素一定在數組A[i..p]中，如果k>p,則第K個元素一定在數組A[p+1..j]，此時，第K個元素在A[p+1..j]中為第k-q個元素(其中q為A[i..p]數組中元素的個數)。依次遞歸下去便可以找到第K個元素。
 時間復雜度
設T(n)為在長度為n的數組中選擇一個元素的時間，則可以得到遞歸式
T(n)≤(1/n)T(max(1,n-1))+ +O(n)
由此可得T(n) ≤Cn.
所以時間復雜度為O(n)
 實驗源程序
import java.util.Random;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.io.IOException;
public class FindK
{
int[] arr;//存放數列
int size;//數列的容量
FindK(int size)
{//在數列arr中查找第k個元素
this.size=size;
//Random ran=new Random();
arr=new int[size];
System.out.println("請輸入"+size+"個數字:");
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String temp = "1";
for(int i=0;i<size;i++)
{//從鍵盤上讀入數列，數字之間以回車分隔
try
{
temp=bf.readLine();
}
catch(IOException ioe){}
try
{
arr[i]=Integer.parseInt(temp);
}
catch(NumberFormatException nfe)
{
System.out.println("你的輸入不合法");
}
}
}
int quickSort(int p,int r,int k)
{//進行快速排序
int q;
int m;
int temp;
if(p==r) return(arr[p]);
q=partition(p,r,arr[p]);
temp=q-p+1;
if(k<=temp){m=quickSort(p,q,k); return m;}
else {m=quickSort(q+1,r,k-temp); return m;}
}
int partition(int p,int r,int keyword)
{//進行劃分
int i,j;
int temp;
i=p;
j=r;
while(true)
{
for(;arr[j]>keyword;j--){}
for(;arr[i]<keyword;i++){}
if(i<j){temp=arr[i];arr[i]=arr[j];arr[j]=temp;}
else return(j);
}
}
void display()
{
String str="";
for(int i=0;i<size;i++)
{
str+=str.format("%8d",arr[i]);
}
System.out.println(str);
}
public static void main(String args[])
{
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
String sSize = "1";
int iSize = 1;
while(true)
{
System.out.println("請輸入數列的容量:");
try
{
sSize = bf.readLine();//從鍵盤讀入數列容量
}catch(IOException ioe){}
try
{
iSize = Integer.parseInt(sSize);
}catch(NumberFormatException nfe)
{
System.out.println("你的輸入不合法");
continue;//進入下次循環
}
break;
}

FindK fk=new FindK(iSize);
int k=1;
long t;
fk.display();
String sn = "1";
while(true)
{
System.out.println("你要查找第幾個元素？");
try
{
sn=bf.readLine();
}
catch(IOException ioe){}
try
{
k=Integer.parseInt(sn);
}
catch(NumberFormatException nfe)
{
System.out.println("你的輸入不合法");
continue;
}
if(k<1||k>fk.size)
{//輸入不合法
System.out.println("你的輸入不合法");
continue;
}
break;//輸入合法則結束循環
}

t=System.currentTimeMillis();
int result = fk.quickSort(0,fk.size-1,k);
t=System.currentTimeMillis()-t;
System.out.println("第"+k+"小元素是 ： "+result);
System.out.println("查找時間為 ： "+t+"ms");
}
}

Ⅱ 編寫一個JAVA應用程序 找出幾個整數中最小的一個

import java.util.Scanner;

public class Test {
public static void main(String[] args)
{
Scanner scanner = new Scanner(System.in);
//從鍵盤輸入數字個數
System.out.println("請輸入數字的個數");
int count = scanner.nextInt();

int[] numberArray = new int[count];
//構造數組
for(int i = 0; i < count; i++){
System.out.println("請輸入第 " + (i + 1) + " 個數字");
int number = scanner.nextInt();
numberArray[i] = number;

}
//查找最小指
int minNumberIndex = 0;
int minNumber = numberArray[minNumberIndex];
for(int i = 0; i < numberArray.length; i++){
if(numberArray[i] < minNumber){
minNumberIndex = i;
minNumber = numberArray[i];
}
}

System.out.println("最小的數是第 " + (minNumberIndex + 1) + " 次輸入的數字，數值是 " + minNumber);
}

}

Ⅲ java編寫程序，找出一維數組中元素的最大值和最小值。

java編寫程序，找出一維數組中元素的最大值和最小值：

方法：

importjava.util.*;
publicclassMain{
publicstaticvoidmain(Stringargs[]){
inta1[]=newint[]{5,3,6,8,10,56};
Arrays.sort(a1);
System.out.println("最大值："+a1[a1.length-1]);
System.out.println("最小值："+a1[0]);
}
}

方法2：

publicclassa{
publicstaticvoidmain(Stringargs[]){
inta[]={84,40,16,3,10,49,28,76,94,70};
intn;
intmin=a[0];
inti;
intmax=a[0];
for(n=0;n<=9;n++){
if(max<a[n])
max=a[n];
}
for(i=0;i<=9;i++){
if(min>a)
min=a;
}
System.out.print("max="+max);
System.out.print("min="+min);
}
}

Ⅳ java中如何找出一串時間序列中的最大，最小值

java.lang.String.compareTo(String)
public int compareTo(String anotherString)按字典順序比較兩個字元串。該比較基於字元串中各個字元的 Unicode 值。將此 String 對象表示的字元序列與參數字元串所表示的字元序列進行比較。如果按字典順序此 String 對象在參數字元串之前，則比較結果為一個負整數。如果按字典順序此 String 對象位於參數字元串之後，則比較結果為一個正整數。如果這兩個字元串相等，則結果為 0；compareTo 只有在方法 equals(Object) 返回 true 時才返回 0。
這是字典排序的定義。如果這兩個字元串不同，則要麼它們在某個索引處具有不同的字元，該索引對二者均為有效索引，要麼它們的長度不同，或者同時具備上述兩種情況。如果它們在一個或多個索引位置上具有不同的字元，假設 k 是這類索引的最小值；則按照 < 運算符確定的那個字元串在位置 k 上具有較小的值，其字典順序在其他字元串之前。這種情況下，compareTo 返回這兩個字元串在位置 k 處的兩個不同的 char 值，即值：

this.charAt(k)-anotherString.charAt(k)
如果它們沒有不同的索引位置，則較短字元串在字典順序上位於較長字元串的前面。這種情況下，compareTo 返回這兩個字元串長度的不同，即值：
this.length()-anotherString.length()

指定者：
介面 Comparable<String> 中的 compareTo
參數：
anotherString - 要比較的 String。
返回：
如果參數字元串等於此字元串，則返回 0 值；如果按字典順序此字元串小於字元串參數，則返回一個小於 0 的值；如果按字典順序此字元串大於字元串參數，則返回一個大於 0 的值。

解決了比較大小的問題，最大值和最小值一個循環搞出來主可以了。

Ⅳ java用快速排序法查找最小的k個元素

quicksort完畢之後，截走前k個元素即可，調用Arrays.sort方法(內部使用的是優化過的quicksort)

Ⅵ java用分治法查找數組元素的最大值和最小值,求大神幫我看看這段代碼錯在哪

分治那個方法基本都錯了：

importjava.util.*;
publicclassMaxmin{
	publicintmax＝0;
	publicintmin＝Integer.MAX_VALUE;
	publicintMin(inta,intb){
		if(a<=b)
			returna;
		else
			returnb;
	}
	publicintMax(inta,intb){
		if(a>=b)
			returna;
		else
			returnb;
	}
	
	publicvoidmin_max(inta[]){
		if(a.length==1){
			max=Max(max,a[0]);
			min=Min(min,a[0]);
		}else{
			intm[]=newint[a.length/2];
			intn[]=newint[a.length-a.length/2];
			System.array(a,0,m,0,m.length);
			System.array(a,m.length,n,0,n.length);
			min_max(m);
			min_max(n);
		}
	}
	publicstaticvoidmain(String[]args){
		Maxminobject=newMaxmin();
		int[]array=newint[100];
		for(inti=0;i<array.length;i++)
		{
			array[i]=(int)(Math.random()*100+1);
			System.out.print(array[i]+"");
		}
		object.min_max(array);
		System.out.println("最大值是："+object.max);
		System.out.println("最小值是："+object.min);
	}
}

Ⅶ 用JAVA語言編譯：數組中包含n個整數，從其中找出k個最小的數，寫出你能想到的最快的方法！！！

最快k*O(n)~O(n)，將前K個數放入一個k的數組中，按序放，對K+1到N的數，依次如果比K數組總的小，將K中最大的取出，放入最小的數，一直維持K個，最後就是最小的K個。

import java.util.Arrays;

/**先給數值里的值進行從小到大排序，取從0到k-1索引的數組值

* @創建一個數組,包含11個元素，求5個最小的數

* @author Administrator

public class ArrayTest {

public static void main(String[] args) {

//最小元素的個數

int k=5;

//創建一個數組,

int[] arr = {1,3,45,33,67,12,88,11,46,32,89};

//操作數組的工具Arrays,sort()方法自動排序，由小到大

Arrays.sort(arr);

for(int i=0;i<k;i++){

System.out.println(arr[i]);

}

(7)用java查找最小k個元素擴展閱讀：

此處數組是程序中聲明的變數數組。它們不同於控制項數組，控制項數組是在設計時通過設置控制項的 Index 屬性規定的。變數數組總是連續的；與控制項數組不同的是，不能從一個數組的中部載入或卸載數組元素。

一個數組中的所有元素具有相同的數據類型（在C、C++、Java、pascal中都這樣。但也並非所有涉及數組的地方都這樣，比如在Visual Foxpro中的數組就並沒這樣的要求）。當然，當數據類型為 Variant 時，各個元素能夠包含不同種類的數據（對象、字元串、數值等等）。可以聲明任何基本數據類型的數組，包括用戶自定義類型和對象變數。