Computer Science 15-110, Spring 2010
Class Notes:  One-Dimensional Arrays

1. Part 1
2. Part 2

One-Dimensional Arrays

1. Part 1

1. Allocation

1. Fixed-Size Array
import java.util.Scanner;
class MyCode {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int[] a = new int[5];
System.out.print("Enter 5 integers: ");
for (int i=0; i<5; i++)
a[i] = scanner.nextInt();
System.out.println("Here are the 5 integers in reverse:");
for (int i=4; i>=0; i--)
System.out.println(a[i]);
}
}
2. Variable-Sized Array
import java.util.Scanner;
class MyCode {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter # of integers: ");
int n = scanner.nextInt();
int[] a = new int[n];
System.out.print("Enter " + n + " integers: ");
for (int i=0; i<n; i++)
a[i] = scanner.nextInt();
System.out.println("Here are the " + n + " integers in reverse:");
for (int i=n-1; i>=0; i--)
System.out.println(a[i]);
}
}
3. Statically-Allocated Array
class MyCode {
public static void main(String[] args) {
int[] a = { 5, 2, 1, 3, 6, 4 };
int n = a.length;
System.out.println("Here are the " + n + " integers in reverse:");
for (int i=n-1; i>=0; i--)
System.out.println(a[i]);
}
}

Or:
class MyCode {
public static void main(String[] args) {
int[] a = new int[] {5, 2, 1, 3, 6, 4 };
int n = a.length;
System.out.println("Here are the " + n + " integers in reverse:");
for (int i=n-1; i>=0; i--)
System.out.println(a[i]);
}
}
4. Statically-Reallocated Array
class MyCode {
public static void main(String[] args) {
int[] a = { 5, 2, 1, 3, 6, 4 };

// now reallocate the array
a = { 1, 3, 5 };  // WILL NOT COMPILE!

int n = a.length;
System.out.println("Here are the " + n + " integers in reverse:");
for (int i=n-1; i>=0; i--)
System.out.println(a[i]);
}
}

Fixed:
class MyCode {
public static void main(String[] args) {
int[] a = { 5, 2, 1, 3, 6, 4 };

// now reallocate the array
a = new int[]{1, 3, 5 };  // Works!!!

int n = a.length;
System.out.println("Here are the " + n + " integers in reverse:");
for (int i=n-1; i>=0; i--)
System.out.println(a[i]);
}
}
2. Default Values

import java.util.Scanner;
class MyCode {
public static void main(String[] args) {
int[] ai = new int[1];
boolean[] ab = new boolean[1];
char[] ac = new char[1];
String[] as = new String[1];
System.out.println("Array default values for:");
System.out.println("  int:     " + ai[0]);
System.out.println("  boolean: " + ab[0]);
System.out.println("  char:    (Unicode " + (int)ac[0] + ")");
System.out.println("  String:  " + as[0]);
}
}

3. Array Parameters

1. Simple Case
class MyCode {
public static void printInReverse(int[] a) {
int n = a.length;
System.out.println("Here are the " + n + " integers in reverse:");
for (int i=n-1; i>=0; i--)
System.out.println(a[i]);
}
public static void main(String[] args) {
int[] a = { 5, 2, 1, 3, 6, 4 };
printInReverse(a);
}
}
2. Modifying array contents is visible to caller
class MyCode {
public static void modifyArrayContents(int[] a) {
a[0] = 99;  // this change IS visible to caller!
}

public static void print(int[] a) {
for (int i=0; i<a.length; i++) System.out.print(a[i] + " ");
System.out.println();
}

public static void main(String[] args) {
int[] a = { 1, 2, 3 };
print(a); // prints 1, 2, 3
modifyArrayContents(a); // works as expected
print(a); // prints 99, 2, 3
}
}
3. Modifying array reference is not visible to caller
class MyCode {
public static void modifyArrayReference(int[] a) {
a = new int[]{ 99, 100 };  // this change IS NOT visible to caller!
}

public static void print(int[] a) {
for (int i=0; i<a.length; i++) System.out.print(a[i] + " ");
System.out.println();
}

public static void main(String[] args) {
int[] a = { 1, 2, 3 };
print(a); // prints 1, 2, 3
modifyArrayReference(a); // does NOT work as expected
print(a); // prints 1, 2, 3
}
}
4. Array Return Types

import java.util.*;
class MyCode {
public static final Random random = new Random();
public static int[] getArrayOfRandoms(int n) {
int[] a = new int[n];
for (int i=0; i<n; i++)
a[i] = random.nextInt(100);
return a;
}
public static void main(String[] args) {
int[] a = getArrayOfRandoms(10);
System.out.println("Here are the randoms: ");
for (int i=0; i<a.length; i++)
System.out.println(a[i]);
}
}

5. Traversal

1. Forward Traversal
class MyCode {
public static void main(String[] args) {
int[] a = { 3, 2, 4, 1 };
System.out.println("Forward Traversal:");
for (int i=0; i<a.length; i++)
System.out.println(a[i]);
}
}
2. Backward Traversal
class MyCode {
public static void main(String[] args) {
int[] a = { 3, 2, 4, 1 };
System.out.println("Backward Traversal:");
for (int i=a.length-1; i>=0; i--)
System.out.println(a[i]);
}
}
3. Alternative Backward Traversal
class MyCode {
public static void main(String[] args) {
int[] a = { 3, 2, 4, 1 };
System.out.println("Alternative Backward Traversal:");
for (int i=0; i<a.length; i++)
System.out.println(a[(a.length-1)-i]);
}
}
6. Arrays Methods

1. equals
import java.util.Arrays;
class MyCode {
public static void main(String[] args) {
int[] a = { 3, 4, 2, 1 };
int[] b = { 3, 4, 2, 1 };
int[] c = { 3, 4, 2 };
System.out.println(Arrays.equals(a, b));
System.out.println(Arrays.equals(a, c));
}
}
2. toString
import java.util.Arrays;
class MyCode {
public static void main(String[] args) {
int[] a = { 3, 4, 2, 1 };
System.out.println(a);  // surprised?
System.out.println(Arrays.toString(a));
}
}
3. fill
import java.util.Arrays;
class MyCode {
public static void main(String[] args) {
int[] a = { 3, 4, 2, 1 };
System.out.println(Arrays.toString(a));
Arrays.fill(a, 9);
System.out.println(Arrays.toString(a));
}
}
4. sort
import java.util.Arrays;
class MyCode {
public static void main(String[] args) {
int[] a = { 3, 4, 2, 1 };
System.out.println(Arrays.toString(a));
Arrays.sort(a);
System.out.println(Arrays.toString(a));
}
}
5. Online Arrays API
http://java.sun.com/j2se/1.5.0/docs/api/java/util/Arrays.html

2. Part 2

1. Swap

1. Broken Swap
import java.util.Arrays;
class MyCode {
public static void brokenSwap(int x, int y) {
int temp = x;
x = y;
y = temp;
}
public static void main(String[] args) {
int[] a = { 3, 4, 2, 1 };
System.out.println(Arrays.toString(a));
brokenSwap(a[0], a[1]);
System.out.println(Arrays.toString(a));
}
}
2. Working Swap
import java.util.Arrays;
class MyCode {
public static void swap(int[] a, int i, int j) {
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
public static void main(String[] args) {
int[] a = { 3, 4, 2, 1 };
System.out.println(Arrays.toString(a));
swap(a,0,1);
System.out.println(Arrays.toString(a));
}
}
2. Copy

1. Broken Copy
import java.util.Arrays;
class MyCode {
public static void main(String[] args) {
int[] a = { 1, 2, 3};
int[] copy = a; // BROKEN!!!  Not a COPY of a!
// After we copy the array, we change the original
// and the copy, but what happens...?
a[0] = 99;
copy[1] = -99;
System.out.println(Arrays.toString(a));
System.out.println(Arrays.toString(copy));
}
}
2. Working Copy
import java.util.Arrays;
class MyCode {
public static int[] copy(int[] a) {
int[] copy = new int[a.length];
for (int i=0; i<a.length; i++)
copy[i] = a[i];
return copy;
}
public static void main(String[] args) {
int[] a = { 1, 2, 3};
int[] copy = copy(a);
// After we copy the array, we change the original
// and the copy, but what happens...?
a[0] = 99;
copy[1] = -99;
System.out.println(Arrays.toString(a));
System.out.println(Arrays.toString(copy));
}
}
3. Equals

1. Broken Equals
class MyCode {
public static void main(String[] args) {
int[] a = { 1, 2, 3};
int[] b = { 1, 2, 3};
System.out.println(a == b);  // surprised?
}
}
Working Equals
import java.util.Arrays;
class MyCode {
public static void main(String[] args) {
int[] a = { 1, 2, 3};
int[] b = { 1, 2, 3};
System.out.println(Arrays.equals(a,b));
}
}
4. Insertion

import java.util.Arrays;
class MyCode {
public static int[] add(int[] a, int newValue) {
int[] result = new int[a.length+1];
for (int i=0; i<a.length; i++)
result[i] = a[i];
result[a.length] = newValue;
return result;
}
public static void main(String[] args) {
int[] a = new int[0];
System.out.println(Arrays.toString(a));
System.out.println(Arrays.toString(a));
System.out.println(Arrays.toString(a));
}
}

5. Deletion

import java.util.Arrays;
class MyCode {

// Removes every occurrence of value, if any, in the array "a"
public static int[] remove(int[] a, int value) {
int[] result = new int[a.length - count(a,value)];
int resultI = 0;
for (int i=0; i<a.length; i++)
if (a[i] != value) {
result[resultI] = a[i];
resultI++;
}
return result;
}
// Helper method for remove.  Returns the number of times that
// value occurs in the array a.
public static int count(int[] a, int value) {
int count = 0;
for (int i=0; i<a.length; i++)
if (a[i] == value)
count++;
return count;
}
public static void main(String[] args) {
int[] a = { 2, 3, 5, 3, 1, 4 };
System.out.println(Arrays.toString(a));
a = remove(a, 1);
System.out.println(Arrays.toString(a));
a = remove(a, 3);
System.out.println(Arrays.toString(a));
}
}

6. Examples

1. The Locker Problem
import java.util.*;
class MyCode {
public static void main(String[] args) {
// 1. Read in # of lockers
Scanner scanner = new Scanner(System.in);
System.out.print("How many lockers: ");
int lockers = scanner.nextInt();

// 2. Allocate array of lockers, all closed at first
//    (We will ignore locker[0].)
boolean[] isOpen = new boolean[lockers+1];

// 3. Student N visits every Nth locker
int student, locker;
for (student=1; student<=lockers; student++) {
for (locker=student; locker<=lockers; locker += student)
isOpen[locker] = !isOpen[locker];
}

// 4. Print out open lockers
System.out.println("Open lockers:");
for (locker=1; locker<=lockers; locker++)
if (isOpen[locker])
System.out.println(locker);
}
}
2. Anagrams
import java.util.*;
class MyCode {
// Returns an array of size 26 containing the counts
// of each of the 26 letters in the given string.
public static int[] charCounts(String s) {
s = s.toUpperCase();
int[] counts = new int[26];
for (int i=0; i<s.length(); i++) {
char c = s.charAt(i);
if ((c >= 'A') && (c <= 'Z'))
++counts[(c - 'A')];
}
return counts;
}
// Two strings are anagrams if the all the counts
// of each of the 26 letters in each string are the same.
public static boolean isAnagram(String s1, String s2) {
int[] counts1 = charCounts(s1);
int[] counts2 = charCounts(s2);
return (Arrays.equals(counts1, counts2));
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
System.out.print("Enter two strings: ");
String s1 = scanner.next();
String s2 = scanner.next();
System.out.println("isAnagram(" + s1 + "," + s2 + ") = " +
isAnagram(s1,s2));
}
}

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem