Este artigo descreve a operação de seleção de tempo linear implementada pelo Java com base no algoritmo de particionamento e conquista. Compartilhe -o para sua referência, como segue:
Problema de seleção de tempo linear: dados n elementos e um número inteiro k, 1≤k≤n, é necessário descobrir o menor elemento desses n elementos (o conjunto linear fornecido aqui é desordenado).
Seleção linear dividida aleatoriamente
O método de divisão aleatória de seleção linear de tempo pode imitar o design do algoritmo randomizado de classificação rápida. A idéia básica é dividir recursivamente a matriz de entrada. Ao contrário da classificação rápida, ele apenas processa recursivamente um dos subarrays divididos.
Explicação do programa: use uma função aleatória para gerar um benchmark de divisão, divida a matriz A [P: r] em dois subarrações a [p: i] e a [i+1: r], para que cada elemento em A [P: I] não seja maior que cada elemento em A [i+1: r]. Então "j = i-p+1" calcula o número de elementos j em um [p: i]. Se k <= j, então o menor elemento em um [P: r] está na sub-matriz a [p: i], e se k> j, o menor elemento K-fés está na sub-matriz a [i+1: r]. Nota: Como se sabe que os elementos da sub-matriz a [P: I] são todos menores que o K-é o pequeno elemento a ser encontrado, o K-é o pequeno elemento em um [P: R] a ser encontrado é o K-é o pequeno elemento em A [i+1: r].
Na pior das hipóteses, por exemplo: quando o menor elemento é sempre encontrado, ele é sempre dividido no maior elemento, que é a complexidade do tempo de O (n^2) . No entanto, a complexidade média do tempo está linearmente relacionada a n, que é O (n)
pacote matemática; importar java.util.scanner; importar java.util.random; public class RandomElect {public static void swap (int x, int y) {int temp = x; x = y; y = temp; } public int Random (int x, int y) {aleatória Random = new Random (); int num = random.nextInt (y)%(y - x + 1) + x; retornar num; } public int partition (int [] list, int baixo, int alto) {int tmp = list [baixo]; // O primeiro da matriz é o eixo central, enquanto (baixo <alto) {while (baixo <High && List [High]> tmp) {High--; } list [baixo] = list [High]; // registros menores que o eixo central são movidos para a extremidade baixa enquanto (Low <High && List [Low] <TMP) {Low ++; } list [High] = List [Low]; // registros maiores que o eixo central são movidos para a lista de ponta} [baixa] = tmp; // registros maiores que o eixo central são retornados baixos; // retorna à posição do eixo central} public int randomizedPartition (int [] matrizes, int esquerda, int direita) {int i = aleatória (esquerda, direita); troca (matrizes [i], matrizes [à esquerda]); Partição de retorno (matrizes, esquerda, direita); } public int randomizedSelect (int [] matrizes, int esquerda, int k) {if (esquerda == direita) {retorna matrizes [esquerda]; } int i = randomizedPartition (matrizes, esquerda, direita); int j = i - esquerda + 1; if (k <= j) {return randomizedSelect (matrizes, esquerda, i, k); } else {return randomizedSelect (matrizes, i+1, certo, kj); }} public static void main (string args []) {System.out.println ("Wulin.com Resultado do teste:"); int [] a = {7,5,3,4,8,6,9,1,2}; for (int i = 0; i <9; i ++) {System.out.print (a [i]+""); } System.out.println (); RandomElect r = new RandomSelect (); System.out.println ("Para que menor elemento você deseja consultar na matriz?"); @Suppresswarnings ("recursos") scanner sc = new scanner (system.in); int m = sc.nextInt (); int n = r.RandomizedSelect (a, 0,8, m); System.out.println ("o" th "nesta matriz" + m + "O menor elemento é:" + n); }}Resultados em execução:
Para obter mais informações sobre os algoritmos Java, os leitores interessados neste site podem visualizar os tópicos: "Estrutura de dados Java e tutorial de algoritmo", "Resumo das dicas de nó da operação Java Dom", "Resumo de dicas de operação de Java e Operação de Java" e "Resumo de Java cache" Tips "TIPS"
Espero que este artigo seja útil para a programação Java de todos.