Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Dada uma coleção de n valores, um elemento k é dito majoritário se a quantidade dele é maior que a metade do
- tamanho da coleção. Gerar uma pilha com n elementos e, em seguida, verificar se ela tem um elemento majoritário.
- Caso tenha, apresente-o.
- */
- package war.paz;
- import java.util.ArrayDeque;
- import java.util.Deque;
- import java.util.Random;
- public class Maine{
- public static void main(String e[]){
- Random r = new Random();
- Deque<Integer> stack = new ArrayDeque<Integer>(); // A pilha
- int size = 10;
- for(int i = 0; i < size; i++){
- stack.addFirst(r.nextInt(3)); // Vamos encher ela de elementos!
- }
- System.out.println(stack); // Ver como tá
- sort(stack); // Ordenar
- System.out.println(stack); // E ver como ficou depois de ordenar
- // Bem, nós sabemos de uma coisa: se há um elemento majoritário, ele também é a mediana
- int x = median(stack,stack.size());
- // Agora só precisamos verificar o número de vezes que nossa mediana aparece na pilha...
- if(timesN(stack,x) > size/2){
- System.out.println("Há um elemento majoritário, e é o " + x);
- }else{
- System.out.println("Não há um elemento majoritário =(");
- }
- }
- public static int timesN(Deque<Integer> k, int x){
- int n = 0;
- int size = k.size();
- for(int i = 0; i < size; i++){
- if(k.peek() == x){
- k.pop();
- n++;
- }else{
- k.pop();
- }
- }
- return n;
- }
- public static int median(Deque<Integer> k, int size){
- int ret = 0;
- if(k.size() == size/2){
- return k.peek();
- }
- int j = k.pop();
- ret = median(k,size);
- k.push(j);
- return ret;
- }
- public static void sort(Deque<Integer> k) {
- if(!k.isEmpty()){
- int i = k.pop(); // yay, k-pop
- sort(k);
- insert(i, k);
- }
- }
- private static void insert(Integer x, Deque<Integer> k) {
- if(k.isEmpty()){
- k.push(x);
- return;
- }
- if(x < k.peek()){
- int i = k.pop();
- insert(x, k);
- k.push(i);
- }else{
- k.push(x);
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement