public class MostOftenOccurring{
public static int occursMostOften(int[] a){
int[] b = new int[a.length];
for (int i = 0; i < a.length; i++){
b[i] = CountOccurrences.countOccurrences(a, a[i]);
}
for (int j = 0; j < b.length; j++){
if (Maximum.maximum(b) == b[j]){
return b[j];
}
}
return 666; //I did this to make the compiler happy
}
public static void main(String[] args){
int[] testArray = {1};
System.out.println(occursMostOften(testArray));
}
}
Is there any way that return 666; could ever be executed?
Name:
Anonymous2009-11-03 2:38
edit: testArray should be something like {1, 3, 4, 2, 6, 2, 1} and the method will return 2 because it is the element that occurs most often in this array
There are a number of ways, for example if a is empty. You are retarded anyway. You do not need an O(n2) time and O(n) space method to find the most common element in an array. It can be done in linear time with constant space.
Name:
Anonymous2009-11-03 3:49
Maximum.maximum
I never knew the Java API had a Maximum class. That is insanely retarded.
>>2,3
In Java it doesn't matter if you have On or O(n) code. It is still slow as fuck.
Name:
Anonymous2009-11-03 10:46
>>9
Holy shit, in my CSII class we had to build a table of processing times of different sorting algorithms using Java.
When our professor realized that all of his students were coming up with the same time for each sorting algorithm (due to Java's terrible overhead) he immediately switched all coursework requirements to C.
Name:
Anonymous2009-11-03 10:48
>>10
HA HA! OH WOW!
This is a good argument against java. One of the best I have encountered.
>>1 public class MostOftenOccurring ... CountOccurrences.countOccurrences ... Maximum.maximum
Is this the fabled ENTERPRISE?? Oh wow.
Name:
Anonymous2009-11-03 13:12
>>5
I'm in an introductory course and I was doing the practice problems for my midterm. One of them asked me to write a class called Maximum which defines a method called maximum which finds the max method in the array.
>>3 I know what Big O Notation is from math but they don't care about speed of algorithms in this course.
I am interested though in how to make this quicker.
>>4 could you give me atleast a vague idea of how?
(defun list->frequency-hash-table (list &key (test #'eql))
"Given a list, returns a hashtable keyed by each element in the list,
and the values are each element's frequency in the list."
(let ((counts (make-hash-table :test test)))
(dolist (i list counts)
(symbol-macrolet ((hash (gethash i counts)))
(if hash (incf hash) (setf hash 1))))))
(defun hashtable->alist (ht)
"Converts a hashtable to an association list"
(let (alist)
(maphash #'(lambda (key val)
(push (cons key val) alist))
ht)
alist))
(defun max-occurances-pair (list)
"Returns a cons pair whose car is the most frequent element, and whose cdr is the number of occurances"
(first (sort (hashtable->alist (list->frequency-hash-table list)) #'> :key #'cdr)))
(defun max-occurances (list)
"Returns two values, the most frequent element, and the number of occurances"
(destructuring-bind (val . count) (max-occurances-pair list)
(values val count)))
Anyone having a more elegant solution is welcome to post it. I can't think of one without writing some functions for mapping/searching over hash tables. I believe there's a few utility libraries which already have code for this, but I didn't bother looking them up now.
Name:
Anonymous2009-11-03 15:06
>>24
Oops, made a minor mistake there, even though the other functions would still return correct results since they don't depend on the order of the elements in the alist being correct:
(defun hashtable->alist (ht)
"Converts a hashtable to an association list"
(let (alist)
(maphash #'(lambda (key val)
(push (cons key val) alist))
ht)
(nreverse alist)))
Name:
Anonymous2009-11-03 15:48
>>24
LISP - Taking half a page to do what most languages can do in half a line.
>>26
The first 2 are just util functions, you can find equivalents of them in various libraries. The actual code which performs the task is (first (sort (hashtable->alist (list->frequency-hash-table list)) #'> :key #'cdr))
I could have written it more concise, but it would have been more inefficient/slower.