6.4 Developing Algorithms Using Arrays

Finding Maximum and Minimum of Arrays

We’ve done this in python many times in the past, but in java it will be different. Steps:

  1. Initialize a variable to store a maximum value
  2. Iterate through every element in the list
    • In python we would use for x in list but this isn’t possible now, instead we must use an enhanced for loop
  3. Check if element is greater than max, if so replace
  4. return element
/* function, takes in array of doubles as values */
private double findMax(double [] values) {
    /* Sets max to first number in the list. Min Value could be the min value */
    double max = values[0];

    /* enhanced for loop notation */
    for (double value : values) {
        /* check for max */
        if (value > max) {
            max = value;
        }
    }
    return max;
}

/* run on array */
double[] nums = {1,2,3,4,5,6,2000, 123.123, 1230912839018230.123901823};
System.out.println(findMax(nums));

1.23091283901823E15

Popcorn Hack

Implement a function to find the minimum of the EVEN INDEXED elements in array of integers.

private double findMinEven(int [] values) {
    /*Function here */
}

int[] nums = {};
System.out.println(findMinEven(nums));

Ok wait but i don’t want to copy this every time. what happened to python’s .max?

double[] nums = {1,2,3,4,5,6,2000};
System.out.println(Arrays.stream(nums).max().getAsDouble())


private double findMinEven(int [] values) {
    /*Function here */
    int min = values[0];
    for (int i = 0; i < values.length; i += 2) {
        if (min > values[i]) {
            min = values[i];
        }
    }
    
    return (double)min;
}

int[] nums = {1,2,3,4,5,6,1,4,1,3,2,2,1,1};
System.out.println(findMinEven(nums));

Shifting Arrays

Oftentimes we need to shift an array. ex. Shifting an array right two: Original: {“a”, “b”, “c”, “d”} Final: {“d”, “c”, “a”, “b”}

How do we do this?

  1. Create a new array
  2. Iterate through each element in the array
  3. Place in appropriate spoce
int [] numbers = {1,2,3,4,5,6,7,8,9,10};

int shift = 8;

/* function */
private int [] shiftRight(int [] values, int shift) {
    /* declare new array */
    int [] shifted = new int [values.length];
    /* iterate through each array */
    for (int index = 0; index < values.length; index++) {
        /*
         Breakdown:
         shifted [new index] = numbers[index] (old value)

         WAIT! but i'm adding a value to somewhere in the middle of the array! 
         we couldn't do that in python but since we specified the type and length of the array, this is possible in java

         Calculating the new index:
         1. we add the shift to the index
         2. handle overflow: we use % to take the modulo operation
         */
        shifted [Math.abs((index + shift) % numbers.length)] = numbers[index];
    }
    return shifted;
}

for ( int value : shiftRight(numbers, shift)) {
    System.out.println(value);
}

3
4
5
6
7
8
9
10
1
2

Challenge Hack: Create a function that iterates through every X items and shifts only those elements Y shift left.

Example: ({1, 2, 3, 4, 5, 6}, Y = 1, X = 2) Output: {5, 2, 1, 4, 3, 6}

Example: ({1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, Y = 2, X = 3) Output: {10, 2, 3, 1, 5, 6, 4, 8, 9, 7}

int [] numbers = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};

int shift = 2;
int space = 4;

/* function */
private int [] shiftRight(int [] values, int shift, int space) {
    /* code here */
}

for ( int value : shiftRight(numbers, shift, space)) {
    System.out.println(value);
}

public class ArrayShift {
    
    public static void shiftEveryXItems(int[] arr, int X, int Y) {
        int n = arr.length;

        for (int i = 0; i < n; i += X) {
            int end = Math.min(i + X, n); 

            shiftLeft(arr, i, end, Y);
        }
    }

    private static void shiftLeft(int[] arr, int start, int end, int Y) {
        int length = end - start;
        Y = Y % length;  

        int[] temp = new int[length];

        for (int i = 0; i < length; i++) {
            temp[i] = arr[(start + i + Y) % length + start];
        }

        for (int i = 0; i < length; i++) {
            arr[start + i] = temp[i];
        }
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 2, 3, 4, 5, 6};
        shiftEveryXItems(nums1, 2, 1);
        System.out.println("Output for Example 1: " + Arrays.toString(nums1)); 

        int[] nums2 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        shiftEveryXItems(nums2, 3, 2);
        System.out.println("Output for Example 2: " + Arrays.toString(nums2)); 
    }
}