Array | Learn for Master

LeetCode Shuffle an Array (Java)

August 23, 2016 Author: david

Shuffle a set of numbers without duplicates.

Example:

// Init an array with set 1, 2, and 3.
int[] nums = {1,2,3};
Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.
solution.shuffle();

// Resets the array back to its original configuration [1,2,3].
solution.reset();

// Returns the random shuffling of array [1,2,3].
solution.shuffle();

1

2

3

4

5

6

7

8

9

10

11

12

13

// Init an array with set 1, 2, and 3.

int[] nums = {1,2,3};

Solution solution = new Solution(nums);

// Shuffle the array [1,2,3] and return its result. Any permutation of [1,2,3] must equally likely to be returned.

solution.shuffle();

// Resets the array back to its original configuration [1,2,3].

solution.reset();

// Returns the random shuffling of array [1,2,3].

solution.shuffle();

Java Solution

public class Solution {

    int[] origin;
    int[] res;
    Random r;
    public Solution(int[] nums) {
        origin = nums;
        res = Arrays.copyOf(nums, nums.length);
        r = new Random();
    }
    
    /** Resets the array to its original configuration and return it. */
    public int[] reset() {
        res = Arrays.copyOf(origin, origin.length);
        return res;
    }
    
    /** Returns a random shuffling of the array. */
    public int[] shuffle() {
        int right = res.length - 1;
        int j;
        
        while(right > 0) {
            j = r.nextInt(right + 1);
            swap(res, j, right);
            right--;
        }
        return res;
    }
    
    void swap(int[] A, int i, int j) {
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(nums);
 * int[] param_1 = obj.reset();
 * int[] param_2 = obj.shuffle();
 */

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

public class Solution {

int[] origin;

int[] res;

Random r;

public Solution(int[] nums) {

origin = nums;

res = Arrays.copyOf(nums, nums.length);

r = new Random();

}

/** Resets the array to its original configuration and return it. */

public int[] reset() {

res = Arrays.copyOf(origin, origin.length);

return res;

}

/** Returns a random shuffling of the array. */

public int[] shuffle() {

int right = res.length - 1;

int j;

while(right > 0) {

j = r.nextInt(right + 1);

swap(res, j, right);

right--;

}

return res;

}

void swap(int[] A, int i, int j) {

int tmp = A[i];

A[i] = A[j];

A[j] = tmp;

}

/**

* Your Solution object will be instantiated and called as such:

* Solution obj = new Solution(nums);

* int[] param_1 = obj.reset();

* int[] param_2 = obj.shuffle();

*/

[Read More...]

Java for Loop

July 30, 2016 Author: david

No comment yet

In this post, I describe how to do for loop on an Java ArrayList. Array, and HashMap.

Java Array for loop

In the following example, we create an int array, then loop it to add numbers from 1 to 100. Then we loop it again to calculate the sum of the numbers in the array.

// Create an array with room for 100 integers
int[] nums = new int[100];

// Fill it with numbers using a for-loop
for (int i = 0; i < nums.length; i++)
    nums[i] = i + 1;  // +1 since we want 1-100 and not 0-99

// Compute sum
int sum = 0;
for (int n : nums)
    sum += n;

// Print the result (5050)
System.out.println(sum);

1

2

3

4

5

6

7

8

9

10

11

12

13

14

// Create an array with room for 100 integers

int[] nums = new int[100];

// Fill it with numbers using a for-loop

for (int i = 0; i < nums.length; i++)

nums[i] = i + 1; // +1 since we want 1-100 and not 0-99

// Compute sum

int sum = 0;

for (int n : nums)

sum += n;

// Print the result (5050)

System.out.println(sum);

Java List for loop

We provide four ways to show how to loop a java List.

import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

public class JavaLoopExample {
    public static void main(String[] argv) {

        String sArray[] = new String[] { "Value 1", "Value 2", "Value 3" };

        // convert array to list
        List<String> list = Arrays.asList(sArray);

        // iterator loop
        System.out.println("iterator.hasNext()");
        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }

        // for loop
        System.out.println("for loop");
        for (int i = 0; i < list.size(); i++) {
            System.out.println(list.get(i));
        }

        // for loop advance
        System.out.println("for loop advance");
        for (String temp : list) {
            System.out.println(temp);
        }

        // while loop;
        System.out.println("while advance");
        int j = 0;
        while (j < list.size()) {
            System.out.println(list.get(j));
            j++;
        }
    }
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

import java.util.Arrays;

import java.util.Iterator;

import java.util.List;

public class JavaLoopExample {

public static void main(String[] argv) {

String sArray[] = new String[] { "Value 1", "Value 2", "Value 3" };

// convert array to list

List<String> list = Arrays.asList(sArray);

// iterator loop

System.out.println("iterator.hasNext()");

Iterator<String> iterator = list.iterator();

while (iterator.hasNext()) {

System.out.println(iterator.next());

}

// for loop

System.out.println("for loop");

for (int i = 0; i < list.size(); i++) {

System.out.println(list.get(i));

}

// for loop advance

System.out.println("for loop advance");

for (String temp : list) {

System.out.println(temp);

}

// while loop;

System.out.println("while advance");

int j = 0;

while (j < list.size()) {

System.out.println(list.get(j));

j++;

}

iterator.hasNext()
Value 1
Value 2
Value 3
for loop
Value 1
Value 2
Value 3
for loop advance
Value 1
Value 2
Value 3
while advance
Value 1
Value 2
Value 3

Java HashMap for loop

If you’re only interested in the keys,

[Read More...]

Leetcode – Search for a Range (Java)

July 27, 2016 Author: david

No comment yet

Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

Analysis:

This problem is equivalent to find the lower bound and upper bound of the target value in the sorted array.

For instance, given a sorted array [1,

[Read More...]

Remove Element from an Array (Java)

July 26, 2016 Author: david

No comment yet

LeetCode – Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example:
Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

Analysis

This problem is similar to another leetcode problem: Remove Duplicates from Sorted Array.

[Read More...]

Remove Duplicates from Sorted Array (Java)

July 26, 2016 Author: david

No comment yet

Leetcode: Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length.

Analysis

We defined two indexes: pre and cur.

[Read More...]

LeetCode – Merge Sorted Array without extra space

July 24, 2016 Author: david

No comment yet

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

Analysis

We have described how to merge two sorted arrays into a third sorted array. For this problem, as A is assumed to have enough space, we are not allowed to create a third array.

We cannot start the merge from the beginning of the two arrays,

[Read More...]

LeetCode – Find the kth largest element in an unsorted array (Java)

July 24, 2016 Author: david

No comment yet

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

Analysis

It’s easy to first sort the array, then pick up the Kth largest element. The time complexity is O(nlogn) if we use quick sort.

Min Heap Based Method

A better method is use a min heap or PriorityQueue with size K.

[Read More...]

LeetCode – Median of Two Sorted Arrays Java Solution

July 24, 2016 Author: david

No comment yet

There are two sorted arrays nums1 and nums2 of size m and n respectively.

Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

1

2

3

4

5

nums1 = [1, 3]

nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

1

2

3

4

nums1 = [1, 2]

nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

Analysis

It is easy to come up with a O(n) solution. Then it is high likely that the interviewer will ask you to give the algorithm with time complexity O(logn).

For any problem with sorted array, to come up with a O(logN) solution, we should consider the binary search related algorithm.

[Read More...]

Leetcode – Reverse Words in a String II (Java)

July 16, 2016 Author: david

No comment yet

Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.

The input string does not contain leading or trailing spaces and the words are always separated by a single space.

For example,
Given s = "the sky is blue",
return "blue is sky the".

Could you do it in-place without allocating extra space?

Analysis

This problem is similar to the rotate array to right by k steps problem.

There are two steps: