More than half of the numbers in the 2010 814/01 array

More than half of the numbers in the [offer-28] array appear

  • Test Points: Arrays
  • Time limit: 1 second
  • Space limitation: 32768K
  • There is a number in the array that appears more than half the length of the array. Find out that number. For example, enter an array of length 9 {1, 2, 3, 2, 2, 2, 5, 4, 2}. Since the number 2 appears five times in the array, more than half the length of the array, output 2. If not, output 0
Ideas:

Idea 1: After array sorting, if the number that meets the criteria exists, it must be the number in the middle of the array. (e.g. 1, 2, 2, 2, 2, 3; or 2, 2, 2, 3, 4; or 2, 3, 4, 4, etc.)
[This method 1 needs to write sort code by itself, and 2 calls Arrays.sort to assist in sorting]
The idea is:

  1. Sort arrays first.
  2. Count the number of times that number appears in the middle and save it in count.
  3. If count occurs more than half the length of the array, return this number, otherwise return 0.
Code:
// Use Arrays.sort() to assist in sorting
import java.util.Arrays;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        Arrays.sort(array);
        int count = 0;
        int num = array[array.length / 2];
        int len = array.length;
        for (int i = 0; i < len; i++) {
            if (array[i] == num) {
                count++;
            }
        }
        if (count > (len / 2)) {
            return num;
        } else {
            return 0;
        }
    }
}
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        // Write Quick Sort by Yourself
        QuickSort(array, 0, array.length - 1);
        int count = 0;
        int num = array[array.length / 2];
        int len = array.length;
        for (int i = 0; i < len; i++) {
            if (array[i] == num) {
                count++;
            }
        }
        if (count > (len / 2)) {
            return num;
        } else {
            return 0;
        }
    }
    public void QuickSort(int[] array, int low, int high) {
        if (low < high) {
            // Find the correct index of benchmark data
            int index = getIndex(array, low, high);
            
            // Iteration
            QuickSort(array, low, index - 1);
            QuickSort(array, index + 1, high);
        }
    }
    
    public int getIndex(int[] array, int low, int high) {
        // Baseline data
        int pivot = array[low];
        while (low < high) {
            // Move the high pointer forward when the element at the end of the queue is greater than or equal to the baseline data
            while (low < high && array[high] >= pivot) {
                high--;
            }
            // If the tail element is less than pivot, it needs to be assigned to low
            array[low] = array[high];
            // When the head element is less than or equal to pivot, move the low pointer forward
            while (low < high && array[low] <= pivot) {
                low++;
            }
             // When the head element is larger than tmp, it needs to be assigned to high
            array[high] = array[low];
        }
        // When jumping out of the loop, low is equal to high, and low or high is the correct index position of tmp.
        // The value of low is not pivot, so you need to assign pivot to arr[low]
        array[low] = pivot;
        return low; // Return the correct location of tmp
    }
    
}
My question:
  1. In Idea 1, count must be greater than half the length of the array. I started by writing conditions greater than or equal to, and some of the sample tests failed.
  2. After reviewing Quick Sorting, Quick Sorting is still not very familiar.
Other ideas 1:

Idea 2: If there are qualified figures, it will appear more times than all other figures and more.
When traversing an array, two values are saved: one is a number in the array, and the other is the number of times. .
When traversing the next number, if it is the same as the previous number, the number of times is increased by 1, otherwise the number of times is reduced by 1; if the number is 0, the next number is saved and the number of times is set to 1. After the traversal, the number saved is the required. Then we can judge whether it meets the requirements.

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int count = 1; // frequency
        int num = array[0]; // Save numbers
        
        int len = array.length;
        for (int i = 1; i < len; i++) {
            if (array[i] == num) {
                count++;
            } else {
                count--;
            }
            if (count == 0) {
                // Update the number to the number currently traversed and set count to 1
                num = array[i];
                count = 1;
            } 
        }

        count = 0;
        // Determine if this number is more than half the length of the array
        for (int i = 0; i < len; i++) {
            if (num == array[i]) {
                count++;
            }
        }
        if (count > len / 2) {
            return num;
        } else {
            return 0;
        }
    }
}

One thing to note here is that count s are set to 1 at the beginning, and then the array traversal starts with the first element.

  • If the first element at this point== num, count++, otherwise count ______________
  • At this point, if count - is executed, count==0. At this point, set num to the first element and continue traversing from the next element.
    The judgment is the same. If the number of occurrences is greater than half the length of the array, return the number, otherwise return 0.
Other ideas 2:

With HashMap.

  • The first is to count the number of occurrences of each number in an array.
  • Then traverse the HashMap.
  • If this value occurs more than half the length, return the value and, after the traversal is over, return 0.
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        int len = array.length;
        for (int i = 0; i < len; i++){
            if (!map.containsKey(array[i])) {
                map.put(array[i], 1);
            } else {
                int count = map.get(array[i]) + 1;
                map.remove(array[i]);
                map.put(array[i], count);
            }
        }
        
        Iterator<Map.Entry<Integer, Integer>> it = map.entrySet().iterator();
        while(it.hasNext()) {
            Map.Entry<Integer, Integer> entry = it.next();
            int key = entry.getKey();
            int val = entry.getValue();
            if (val > len / 2) {
                return key;
            }
        }
        return 0;
    }
}
  • This HashMap iteration is a bit cumbersome to use. Refer to the following blog to see how to use it:
  • (Entry Set () of Map in Java and its usage (four ways of traversing map)
  • Using HashMap, three packages are introduced:
    import java.util.HashMap;
    import java.util.Iterator;
    import java.util.Map;
  • When iterating, specify the data type of the iterator: Iterator < Map. Entry < Integer, Integer >.
  • Iterator to get map: map.entrySet().iterator();
  • Iterate to see if there is a next hasNext() method.
  • Get the key pair: Map. Entry < Integer, Integer > entry = it. next ()
    int key = entry.getKey()
    int value = entry.getValue()

Tags: Java less

Posted on Mon, 02 Sep 2019 01:10:47 -0700 by angershallreign