Найдите наиболее распространенную запись в массиве
Когда вы объявляете ссылочную переменную (т. е. объект), вы действительно создаете указатель на объект. Рассмотрим следующий код, в котором вы объявляете переменную примитивного типа int:
int x;
x = 10;
В этом примере переменная x является int, и Java инициализирует ее для 0. Когда вы назначаете его 10 во второй строке, ваше значение 10 записывается в ячейку памяти, на которую указывает x.
Но когда вы пытаетесь объявить ссылочный тип, произойдет что-то другое. Возьмите следующий код:
Integer num;
num = new Integer(10);
Первая строка объявляет переменную с именем num, но она не содержит примитивного значения. Вместо этого он содержит указатель (потому что тип Integer является ссылочным типом). Поскольку вы еще не указали, что указать на Java, он устанавливает значение null, что означает «Я ничего не указываю».
Во второй строке ключевое слово new используется для создания экземпляра (или создания ) объекту типа Integer и переменной указателя num присваивается этот объект. Теперь вы можете ссылаться на объект, используя оператор разыменования . (точка).
Exception, о котором вы просили, возникает, когда вы объявляете переменную, но не создавали объект. Если вы попытаетесь разыменовать num. Перед созданием объекта вы получите NullPointerException. В самых тривиальных случаях компилятор поймает проблему и сообщит вам, что «num не может быть инициализирован», но иногда вы пишете код, который непосредственно не создает объект.
Например, вы можете имеют следующий метод:
public void doSomething(SomeObject obj) {
//do something to obj
}
В этом случае вы не создаете объект obj, скорее предполагая, что он был создан до вызова метода doSomething. К сожалению, этот метод можно вызвать следующим образом:
doSomething(null);
В этом случае obj имеет значение null. Если метод предназначен для того, чтобы что-то сделать для переданного объекта, целесообразно бросить NullPointerException, потому что это ошибка программиста, и программисту понадобится эта информация для целей отладки.
Альтернативно, там могут быть случаи, когда цель метода заключается не только в том, чтобы работать с переданным в объекте, и поэтому нулевой параметр может быть приемлемым. В этом случае вам нужно будет проверить нулевой параметр и вести себя по-другому. Вы также должны объяснить это в документации. Например, doSomething может быть записано как:
/**
* @param obj An optional foo for ____. May be null, in which case
* the result will be ____.
*/
public void doSomething(SomeObject obj) {
if(obj != null) {
//do something
} else {
//do something else
}
}
Наконец, Как определить исключение & amp; причина использования Трассировки стека
6 ответов
Сохраните одно целое число для каждого бита и увеличьте этот набор соответственно для каждого целого числа в массиве.
В конце, некоторые биты будут иметь количество выше, чем половина длины массива - те биты определяют N. Конечно, количество будет выше, чем количество раз N произошло, но это не имеет значения. Важная вещь состоит в том, что любой бит, который не является частью N , не может происходить больше чем половина времен (потому что N имеет более чем половину записей), и любой бит, который является частью N , должен происходить больше чем половина времен (потому что это произойдет каждый раз, когда N происходит, и любые отдельно оплачиваемые предметы).
(Никакой код в данный момент - собирающийся потерять доступ к сети. Надо надеяться, вышеупомянутое достаточно ясно все же.)
"Линейный Алгоритм Решения большинством голосов Времени Boyer и Moore's" - спускаются по массиву, поддерживающему Ваше текущее предположение в ответе.
Можно сделать это только с двумя переменными.
public uint MostCommon(UInt32[] numberList)
{
uint suspect = 0;
int suspicionStrength = -1;
foreach (uint number in numberList)
{
if (number==suspect)
{
suspicionStrength++;
}
else
{
suspicionStrength--;
}
if (suspicionStrength<=0)
{
suspect = number;
}
}
return suspect;
}
Делают первое число подозрительным числом и продолжают цикличное выполнение через список. Если число соответствует, увеличьте силу подозрения одной; если это не соответствует, понижает силу подозрения одной. Если сила подозрения совершает нападки 0, текущее число становится подозрительным числом. Это будет не работа для нахождения наиболее распространенного числа, только число, которое составляет больше чем 50% группы. Сопротивляйтесь желанию добавить проверку, если suspicionStrength будет больше, чем половина длины списка то - это будет всегда приводить к большему количеству общих сравнений.
P.S. Я не протестировал этот код - используют его в Вашей собственной опасности.
Псевдо код (C++ блокнота:-)) для алгоритма Jon:
int lNumbers = (size_of(arrNumbers)/size_of(arrNumbers[0]);
for (int i = 0; i < lNumbers; i++)
for (int bi = 0; bi < 32; bi++)
arrBits[i] = arrBits[i] + (arrNumbers[i] & (1 << bi)) == (1 << bi) ? 1 : 0;
int N = 0;
for (int bc = 0; bc < 32; bc++)
if (arrBits[bc] > lNumbers/2)
N = N | (1 << bc);
У меня есть воспоминания об этом алгоритме, который мог бы или не мог бы следовать правилу 2K. Это, возможно, должно было бы быть переписано со стеками и т.п., чтобы не повреждать пределы памяти из-за вызовов функции, но это могло бы быть ненужным, так как это только когда-либо имеет логарифмическое количество таких вызовов. Во всяком случае у меня есть неопределенные воспоминания из колледжа или рекурсивного решения этого, которое включило, делят и завоевывают, секрет, являющийся, что, когда Вы разделяете группы пополам, по крайней мере одна из половин все еще имеет больше чем половину своих значений, равных максимум. Основное правило, когда деление состоит в том, что Вы возвращаете два значения вершины кандидата, одно из которых является главным значением и один из которых является некоторым другим значением (который может или не может быть 2-м местом). Я забываю сам алгоритм.
Доказательство правильности для buti-oxa / ответ Jason Hernandez, принимая ответ Jason совпадает с ответом buti-oxa, и оба работают способ, которым описал алгоритм, должен работать:
Мы определяем скорректированную силу подозрения, как являющуюся равным силе подозрения, если главное значение выбрано или - сила подозрения, если главное значение не выбрано. Каждый раз Вы выбираете правильное число, текущие скорректированные увеличения силы подозрения 1. Каждый раз, когда Вы выбираете неправильное число, оно или отбрасывает на 1 или увеличивается на 1, в зависимости от того, если неправильное число в настоящее время выбирается. Так, минимальное возможное окончание корректировалось, сила подозрения равна числу - [главные значения] - числу - [другие значения]