SilMOON

This post is about the “Majority Element” problem and my attempts to it. In this problem, you are given an array of size n with some int numbers and you need to find the “majority element” which appears more than n/2 times.

My first attempt is intuitive: use two loops to traverse the whole array and an if statement and a counter variable to find the majority element. This approach did solve the problem, but wasn’t fast enough to pass the speed test. Here’s the code:

class Solution {
    public int majorityElement(int[] nums) {
        int counter = 1;
        int answer = 0;
        if (nums.length==1){
            answer = nums[0];
        } else{
            for (int i = 0; i < nums.length-1; i++){
                for (int j = i+1; j < nums.length; j++){
                    if (nums[i]==nums[j]){
                        counter++;
                        if (counter > nums.length/2){
                            answer = nums[j];
                            break;
                        }
                    }
                }
                counter = 1;
            }            
        }

        return answer;
    }
}

I didn’t figure out a better solution so I turned to the solution tab. And I saw some good approaches:

I. Sorting
The main idea of this approach is that if an element appears more than n/2 times, if we sort it in an monotonically increasing (or decreasing) order, the element in the middle (the index is (n/2) or (n/2 + 1), depends on the length of the array is odd or even) must be this majority element. So the solution will be very simple:

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

II. HashMap
This approach uses HashMap with element and appears times to find the majority element. The code snippet below is from leetcode:

class Solution {
    private Map<Integer, Integer> countNums(int[] nums) {
        Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
        for (int num : nums) {
            if (!counts.containsKey(num)) {
                counts.put(num, 1);
            }
            else {
                counts.put(num, counts.get(num)+1);
            }
        }
        return counts;
    }

    public int majorityElement(int[] nums) {
        Map<Integer, Integer> counts = countNums(nums);

        Map.Entry<Integer, Integer> majorityEntry = null;
        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
            if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
                majorityEntry = entry;
            }
        }

        return majorityEntry.getKey();
    }
}

I’m doing some algorithm practices recently in Leetcode. This post is about the “Single Number” problem and my attempts to it.

In this problem, you are given an array with some int numbers in pair except one single number and you need to find the single number. The tricky part I think is that you can’t delete an element from an array directly in java so you need to fine another approach to make the single element more “outstanding”.

My first attempt is quite straightforward (and stupid): use a for loop to find the maximum number in the given array and plus it by 1 to generate an invalid number, then use another 2 loops to find elements in pair and turn them into this invalid number. At last, use another loop to find the element which doesn’t equal to the invalid number to get the result. This approach did solve the problem, but the speed is pathetically slow and unsurprisingly, it failed the speed test.

My second attempt got rid of the loop for generating invalid number and the loop for finding the element which is not “invalid”. Instead, I use a variable named “counter”, the counter will become 1 when an element has a duplicate when its “duplicate checking” loop ends, and the counter will be reset to 0 before next checking loop. If an element doesn’t have a duplicate, the counter will still be 0 and the answer will be nums[i], then the program will jump out of the loop directly. Here’s this version’s solution:

class Solution {
    public int singleNumber(int[] nums) {
        int answer = 0;
        int counter = 0;

        for (int i = 0; i < nums.length; i++){
            for (int j = 0; j < nums.length; j++){
                if (nums[i]==nums[j] && i!=j){
                    counter++;
                }
            }
            if (counter == 1){
                counter = 0;
            } else {
                answer = nums[i];
                break;
            }
        }

        return answer;
    }
}

This solution passed the time limited test in most cases but still failed sometimes. Obviously this solution is not fast enough because the two loops for duplicate checking. But I couldn’t figure out a better solution. So I checked the discussion posts of this problem and find a much more better solution than mine:

    int ans =0;
    int len = nums.length;
    for(int i=0; i<len; i++){
        ans ^= nums[i];
    }

    return ans;

This solution uses only one loop and the way it check unduplicated element is using bitwise XOR. The main idea is that 0^N==N and N^N==0. Also, XOR is commutative which means N1^N3^N2^N1^N2 == N1^N1^N2^N2^N3. As a result, the variable ans will always be the single element and the complexity is only O(n)! Brilliant!

As a widely used network protocol, Secure Shell (SSH) provides several authentication approaches. However, we’ll focus on public key authentication only in this article.

Public key cryptography which is also named as asymmetric cryptography uses pairs of keys: public keys and private keys.

The purpose of this project is to create an easy Visual Novel. In this series of blogs, I’ll share some experience in the process of building a game in Ren’Py.

Ren’Py is a AVG engine made by python. The API is python-like and easy to use. The engine based on MIT license. The main direction of Ren’Py engine is galgame which fits my goal.

My OS is Ubuntu 16.04 LTS, and I will use Atom as my editor. The Ren’Py version I use is 6.99.8. To install it in Ubuntu, just input this command in terminal:

sudo apt install renpy

The Ren’Py in Ubuntu’s repository may not be the newest, if you want to get the up-to-date version, check its official website https://www.renpy.org/.

After installing the Ren’Py, you’ll see a icon like this: . Then we can click the “preference” button to begin configuration. The process of configuration is easy, for beginning, we just need to set our editor and project directory. And then click the “Back” button to the main interface. To create a new game, just click “Create New Game” and set a theme you like. The basic frame is found.

The main part of your game will be found in a file named script.rpy. Ren’Py is very friendly to beginners, the comments are specific and easy to understand. In this blog I’ll show some basic syntax.

To create a background picture, we can use image syntax, in the example below, I’ll show how to declare a background picture named light:

image bg light = “light.jpg”

Now we initialise our background picture light. If we want to use the background, we can use the code below in label block to invoke it:

scene bg light

(Tips: Resources like pictures, music should be put in game folder.)

This series will be closed temporarily.

Hi I’m SilMOON, I hope I can learn and share interesting technologies and programming skills by building this blog.