Определить локальные минимумы и максимумы, Java
Я могу использовать методы hasNextInt и getNextInt.
В настоящее время я думаю об алгоритме. Но я не уверен, понимаю ли я логику. Сначала я строю кортеж и сравниваю его числа. Например. Я сравниваю 23 и 7. 7 — локальный минимум. Что бы я тогда сделал? Создайте тройной? Но какие цифры имеют три, 23 7 13 или 13 4 8? Я не уверен.
Скажем, мы сохраняем левый сосед и число в середине трех чисел:
left middle current 0 0 23 23 0 7 23 7 13 minimum 7 Что тогда будет? Установите vars в 0 и начните со следующего числа 4? Или сохраните 7 слева, 13 в середине, чтобы иметь 4 в качестве тока?
Обновление (этот код работает):
int left = 0; int center = 0; while(hasNextInt()) < int current = getNextInt(); if((left != 0) && (center != 0))< if(current >center && center < left)< System.out.println("Min: "+center); left = center; center = current; >else < left = center; center = current; >>else if((left != 0) && (center == 0))< if(left < current)< System.out.println("Min: "+left); center = current; >else < center = current; >>else if((left == 0) && (center == 0)) < left = current; >> if(left > center)
Спасибо за вашу помощь!
Lost in OWL 29 окт. 2010, в 12:51
Поделиться
Поделиться:
comparison
4 ответа
Лучший ответ
То, что у вас там, похоже на хорошее начало.
Однако смотреть только на кортежи будет недостаточно, потому что вы должны посмотреть на три числа, чтобы обнаружить локальный минимум, поэтому вам придется расширить свой алгоритм.
Чтобы понять, как это сделать, попробуйте выполнить простой пример на бумаге. Как бы вы могли вручную найти локальные минимумы? Можете ли вы сделать что-то подобное в своей программе?
Не стесняйтесь публиковать обновленную версию вашей программы (редактируя вопрос, добавляя новый код в конец), а затем мы можем помочь, если вы все еще застряли.
Отвечайте на свое редактирование:
Что тогда будет? Установите вары на 0 и начать со следующего числа 4? Или сохраните 7 слева, 13 в середине иметь 4 как текущий?
Вы не можете просто установить все на 0; вам все равно понадобятся последние два номера вашей тройки, чтобы начать следующую тройку, потому что ваши тройки ведут себя как окна, скользящие по списку чисел (это часто называют техникой «скользящего окна», как это использует многие алгоритмы).
Вы можете скопировать номера в свои новые переменные вручную.
Для большей элегантности вы можете реализовать это в отдельном классе «Триплет». Идеи для рассмотрения: этот класс может проверить минимальные значения и позволить вам добавить новый номер, автоматически «выталкивая» самое старое число.
Найдите локальные минимумы в массиве
Рекомендуется: сначала попробуйте свой подход в , прежде чем переходить к решению.
Простое решение — выполнить линейное сканирование массива, и как только мы найдем локальный минимум, мы вернем его. В худшем случае временная сложность этого метода будет O (n). Эффективное решение основано на двоичном поиске. Сравниваем средний элемент с его соседями. Если средний элемент не больше любого из своих соседей, мы возвращаем его. Если средний элемент больше, чем его левый сосед, то в левой половине всегда есть локальные минимумы (почему? Возьмите несколько примеров). Если средний элемент больше, чем его правый сосед, то всегда есть локальные минимумы в правой половине (по той же причине, что и левая половина). Below is the implementation of the above idea :
C++
// A C++ program to find a local minima in an array
// A binary search based function that returns
// index of a local minima.
int localMinUtil( int arr[], int low, int high, int n)
// Find index of middle element
int mid = low + (high — low)/2; /* (low + high)/2 */
// Compare middle element with its neighbours
// (if neighbours exist)
if ((mid == 0 || arr[mid-1] > arr[mid]) &&
(mid == n-1 || arr[mid+1] > arr[mid]))
return mid;
// If middle element is not minima and its left
// neighbour is smaller than it, then left half
// must have a local minima.
else if (mid > 0 && arr[mid-1] < arr[mid])
return localMinUtil(arr, low, (mid -1), n);
// If middle element is not minima and its right
// neighbour is smaller than it, then right half
// must have a local minima.
return localMinUtil(arr, (mid + 1), high, n);
// A wrapper over recursive function localMinUtil()
int localMin( int arr[], int n)
return localMinUtil(arr, 0, n-1, n);
/* Driver program to check above functions */
int n = sizeof (arr)/ sizeof (arr[0]);
printf ( «Index of a local minima is %d» ,
localMin(arr, n));
Java
// A Java program to find a local minima in an array
import java.io.*;
// A binary search based function that returns
// index of a local minima.
public static int localMinUtil( int [] arr, int low,
int high, int n)
// Find index of middle element
int mid = low + (high — low) / 2 ;
// Compare middle element with its neighbours
// (if neighbours exist)
if (mid == 0 || arr[mid — 1 ] > arr[mid] && mid == n — 1 ||
arr[mid] < arr[mid + 1 ])
return mid;
// If middle element is not minima and its left
// neighbour is smaller than it, then left half
// must have a local minima.
else if (mid > 0 && arr[mid — 1 ] < arr[mid])
return localMinUtil(arr, low, mid — 1 , n);
// If middle element is not minima and its right
// neighbour is smaller than it, then right half
// must have a local minima.
return localMinUtil(arr, mid + 1 , high, n);
// A wrapper over recursive function localMinUtil()
public static int localMin( int [] arr, int n)
return localMinUtil(arr, 0 , n — 1 , n);
public static void main (String[] args)
int n = arr.length;
System.out.println( «Index of a local minima is » + localMin(arr, n));
//This code is contributed by Dheerendra Singh
Python3
# Python3 program to find a
# local minima in an array
# A binary search based function that
# returns index of a local minima.
def localMinUtil(arr, low, high, n):
# Find index of middle element
mid = low + (high — low) / / 2
# Compare middle element with its
# neighbours (if neighbours exist)
if (mid = = 0 or arr[mid — 1 ] > arr[mid] and
mid = = n — 1 or arr[mid] < arr[mid + 1 ]):
return mid
# If middle element is not minima and its left
# neighbour is smaller than it, then left half
# must have a local minima.
elif (mid > 0 and arr[mid — 1 ] < arr[mid]):
return localMinUtil(arr, low, mid — 1 , n)
# If middle element is not minima and its right
# neighbour is smaller than it, then right half
# must have a local minima.
return localMinUtil(arr, mid + 1 , high, n)
# A wrapper over recursive function localMinUtil()
def localMin(arr, n):
return localMinUtil(arr, 0 , n — 1 , n)
# Driver code
arr = [ 4 , 3 , 1 , 14 , 16 , 40 ]
n = len (arr)
print ( «Index of a local minima is » ,
localMin(arr, n))
# This code is contributed by Anant Agarwal.
C#
// A C# program to find a
// local minima in an array
using System;
// A binary search based function that returns
// index of a local minima.
public static int localMinUtil( int [] arr, int low,
int high, int n)
// Find index of middle element
int mid = low + (high — low) / 2;
// Compare middle element with its neighbours
// (if neighbours exist)
if (mid == 0 || arr[mid — 1] > arr[mid] &&
mid == n — 1 || arr[mid] < arr[mid + 1])
return mid;
// If middle element is not minima and its left
// neighbour is smaller than it, then left half
// must have a local minima.
else if (mid > 0 && arr[mid — 1] < arr[mid])
return localMinUtil(arr, low, mid — 1, n);
// If middle element is not minima and its right
// neighbour is smaller than it, then right half
// must have a local minima.
return localMinUtil(arr, mid + 1, high, n);
// A wrapper over recursive function localMinUtil()
public static int localMin( int [] arr, int n)
return localMinUtil(arr, 0, n — 1, n);
// Driver Code
public static void Main ()
int n = arr.Length;
Console.WriteLine( «Index of a local minima is » +
localMin(arr, n));
// This code is contributed by vt_m.
PHP
// A PHP program to find a
// local minima in an array
// A binary search based
// function that returns
// index of a local minima.
function localMinUtil( $arr , $low , $high , $n )
// Find index of middle element
/* (low + high)/2 */
$mid = $low + ( $high — $low ) / 2;
// Compare middle element
// with its neighbours
// (if neighbours exist)
if (( $mid == 0 or $arr [ $mid — 1] > $arr [ $mid ]) and
( $mid == $n — 1 or $arr [ $mid + 1] > $arr [ $mid ]))
return $mid ;
// If middle element is not
// minima and its left
// neighbour is smaller than
// it, then left half
// must have a local minima.
else if ( $mid > 0 and $arr [ $mid — 1] < $arr [ $mid ])
return localMinUtil( $arr , $low , ( $mid — 1), $n );
// If middle element is not
// minima and its right
// neighbour is smaller than
// it, then right half
// must have a local minima.
return localMinUtil(arr, (mid + 1), high, n);
// A wrapper over recursive
// function localMinUtil()
function localMin( $arr , $n )
return floor (localMinUtil( $arr , 0, $n — 1, $n ));
// Driver Code
$arr = array (4, 3, 1, 14, 16, 40);
$n = count ( $arr );
echo «Index of a local minima is » ,
localMin( $arr , $n );
// This code is contributed by anuj_67.
Index of a local minima is 2
Сложность времени: O (Log n)
Связанная проблема:
Найдите пиковый элемент Эта статья предоставлена Рошни Агарвалом . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью на сайте deposit.geeksforgeeks.org или отправить свою статью по электронной почте: grant@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше. Вниманию читателя! Не переставай учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию . Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.
Локальный минимум в списке
Необходимо реализовать функцию, которая из элементов переданного списка целых чисел составит новый список, состоящий из всех элементов переданного списка за исключением локальных минимумов. Локальный минимум — элемент, который строго меньше соседей слева и справа (для элемента[0] — справа, для последнего — слева). Обращаться к элементам по индексу запрещено, перебирать элементы с помощью цикла for (int value: list)
Проблема следующая: Если в списке имеются два одинаковых элемента, причем один из них является локальным минимум, то в новый список не добавляются оба (хотя должен не добавиться только тот, который является локальным минимумом). Ниже прикрепляю фрагмент кода.
static List list(List list) < ListnewList = new ArrayList<>(); for (Integer value : list) < if (!isLocalMin(list, value)) < newList.add(value); >> return newList; > static boolean isLocalMin(List list, int number) < Integer bufferNum = 0; Integer bufferLeft = 0; for (Integer value : list) < if (value == number) < bufferLeft = bufferNum; bufferNum = number; >else < if (bufferLeft >bufferNum && value > bufferNum) < return true; >bufferNum = value; bufferLeft = bufferNum; > > return false; > Отслеживать
user328896
задан 22 янв 2020 в 20:56
15 5 5 бронзовых знаков
Я исправил ошибку с последним элементом.
22 янв 2020 в 21:29
1 ответ 1
Сортировка: Сброс на вариант по умолчанию
Это делается одним циклом:
function f(arr) < var res = [] var l, c, r var first = true for (r of arr) < if (first) < l = Infinity c = r first = false >else < if (!(c < l && c < r)) < res.push(c) >l = c c = r > > if (c >= l) < res.push(c) >return res > var a = Array.from(, () => Math.random()*100 | 0) console.log(a.join(", ") + "\n" + f(a).join(", "))Найти число локальных минимумов
Количество локальных максимумов/минимумов
Как подсчитать количество локальных максимумов/минимумов в массиве? Не получается никак import.
найти число локальных минимумов
условие: В целочисленной квадратной матрице a = a для всех допустимых i и j. Соседями элемента.
295 / 468 / 86
Регистрация: 26.02.2018
Сообщений: 931
Записей в блоге: 2
Сообщение от wlls 
Нужно написать программу
Так «пилите, Шурочка, пилите. »
2495 / 1944 / 486
Регистрация: 17.02.2014
Сообщений: 9,239
wlls, так пойдет?
1 2 3 4 5 6
public class Helper { public static void main(String[] args) { System.out.println("Локальный минимум!"); } }
или ты сш закончишь, а потом возьмешься за программирование?
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
Помогаю со студенческими работами здесь
Найти максимальный из локальных минимумов массива
Дан массив размера N. Найти максимальный из его локальных минимумов (локальный минимум — это.
Найти максимум среди локальных минимумов
Задача в том, чтобы найти максимум локального минимума. Уже триллиона раз прочитала, что.
Найти максимальный из локальных минимумов массива
Дан массив размера N. Найти максимальный из его локальных минимумов (локальный минимум — это.
Найти максимальный из локальных минимумов массива
Дан массив размера N. Найти максимальный из его локальных минимумов (локальный минимум — это.
Найти в массиве количество локальных минимумов
Привет. Нужна помощь в задачках, т.к. уеду до 31 числа. Не будет интернета и ПК. Дан массив.