Z OLD Tutorial 02 - james-bern/CS136 GitHub Wiki

Problems

I recommend working in order from 🟢 to 🟦 to ♦️.

import java.util.*;

class Tut02 {
    // // Difficulty: ()
    // ({ 5, 4, 7, 0, 0, 7 }, 7) -> 2
    // return -1 if value not found
    static int findIndexOfFirstOccurrence(int[] array, int value) {
        return -1;
    }
    
    // // Difficulty: []
    // ({ 1, 3, 3, 2, 3, 4 }, 3) -> { 1, 2, 4 }
    static int[] removeAllOccurrences(int[] array, int value) {
        return null;
    }
    
    // // Difficulty: <>
    // { { 1, 3 }, { 2, 4, 5, 7 }, { 0, 5 } } -> { 0, 1, 2, 3, 4, 5, 5, 7 }
    // result must still be sorted
    // you shouldn't have to call a sorting function
    static int[] mergeArrayOfSortedArrays(int[][] arrays) {
        return null;
    }
    
    public static void main(String[] arguments) {
        {
            System.out.print("(): ");
            int[] array = { 5, 4, 7, 0, 0, 7 };
            System.out.println(findIndexOfFirstOccurrence(array, 7));
        }
        
        {
            System.out.print("[]: ");
            int[] array = { 1, 3, 3, 2, 3, 4 };
            System.out.println(Arrays.toString(removeAllOccurrences(array, 3)));
            
        }
        
        {
            System.out.print("<>: ");
            int[][] arrays = { { 1, 3 }, { 2, 4, 5, 7 }, { 0, 5 } }; 
            System.out.println(Arrays.toString(mergeArrayOfSortedArrays(arrays)));
        }
    }
}

Solutions

import java.util.*;

class Tut02 {
    // // Difficulty: ()
    // ({ 5, 4, 7, 0, 0, 7 }, 7) -> 2
    // return -1 if value not found
    static int findIndexOfFirstOccurrence(int[] array, int value) {
        for (int i = 0; i < array.length; ++i) {
            if (array[i] == value) {
                return i;
            }
        }
        return -1;
    }

    // // Difficulty: []
    // ({ 1, 3, 3, 2, 3, 4 }, 3) -> { 1, 2, 4 }
    // you should NOT have to use any fancy array functions; just new int[] and for loops
    static int[] removeAllOccurences(int[] array, int value) {
        int[] result; {
            int resultLength = 0;
            for (int i = 0; i < array.length; ++i) {
                if (array[i] != value) {
                    ++resultLength;
                }
            }
            result = new int[resultLength];
        }

        int resultIndex = 0;
        for (int i = 0; i < array.length; ++i) {
            if (array[i] != value) {
                result[resultIndex++] = array[i];
            }
        }

        return result;
    }

    // // Difficulty: <>
    // { { 1, 3 }, { 2, 4, 5, 7 }, { 0, 5 } } -> { 0, 1, 2, 3, 4, 5, 5, 7 }
    // result must still be sorted
    // you should NOT have to call a general-purpose sorting function
    static int[] mergeArrayOfSortedArrays(int[][] arrays) {
        // indices of the next unmerged element in the inner arrays
        // (starts out as { 0, 0, ..., 0 }
        int[] nextInnerIndices = new int[arrays.length];

        int[] result; {
            int resultLength = 0;
            for (int i = 0; i < arrays.length; ++i) {
                resultLength += arrays[i].length;
            }
            result = new int[resultLength];
        }

        int resultIndex = 0;
        while (resultIndex < result.length) {
            // copy the smallest of the next elements into result
            // and increment the corresponding index in nextInnerIndices
            int minValue = Integer.MAX_VALUE;
            int minOuterIndex = -1;
            for (int i = 0; i < arrays.length; ++i) {
                int j = nextInnerIndices[i];
                if (j >= arrays[i].length) { continue; }
                if (arrays[i][j] < minValue) {
                    minValue = arrays[i][j]; 
                    minOuterIndex = i;
                }
            }
            assert minOuterIndex != -1;
            result[resultIndex++] = minValue;
            ++nextInnerIndices[minOuterIndex];
        }
        return result;
    }

    public static void main(String[] arguments) {
        {
            System.out.print("(): ");
            int[] array = { 5, 4, 7, 0, 0, 7 };
            System.out.println(findIndexOfFirstOccurrence(array, 7));
        }

        {
            System.out.print("[]: ");
            int[] array = { 1, 3, 3, 2, 3, 4 };
            System.out.println(Arrays.toString(removeAllOccurences(array, 3)));

        }

        {
            System.out.print("<>: ");
            int[][] arrays = { { 1, 3 }, { 2, 4, 5, 7 }, { 0, 5 } }; 
            System.out.println(Arrays.toString(mergeArrayOfSortedArrays(arrays)));
        }
    }
}