Каков наиболее эффективный способ найти наиболее распространенное значение в векторе?

Question

Я пытаюсь создать функцию для решения этой загадки:

Арифметическая прогрессия определяется как та, в которой существует постоянная разница между последовательными членами данной серии чисел.Вам предоставляются последовательные элементы арифметической прогрессии.Однако есть одна загвоздка: ровно один термин из оригинальной серии отсутствует в наборе чисел, которые вам дали.Остальная часть данной серии совпадает с оригинальной AP.Найти пропущенный термин.

Необходимо написать функцию findMissing (список), список всегда будет не менее 3 цифр.Отсутствующий термин никогда не будет первым или последним.

В следующем разделе кода показана моя попытка использования этой функции.Сайт, на котором я работаю, выполняет тесты против этой функции, и все они пройдены, поскольку они выводят правильное пропущенное целое число.

Проблема, с которой я сталкиваюсь, заключается в том, что она выдает ошибку тайм-аута, поскольку она требуетдолго бегать все тесты.Есть 102 теста, и он говорит, что для их завершения требуется более 12 секунд.Более 12 секунд означают, что функция недостаточно эффективна.

После выполнения моих собственных временных тестов в RStudio кажется, что запуск функции займет значительно меньше времени, чем 12 секунд, но независимо от того, нужно ли мне это делатьболее эффективно, чтобы иметь возможность завершить головоломку.

Я спросил на форуме сайта, и кто-то сказал: «Сортировка стоит дорого, придумайте другой способ сделать это без нее».Я понял, что это означает, что я не должен использовать функцию sort ().Это то, что они имеют в виду?

С тех пор я нашел несколько разных способов получения my_diff, который вычисляется с помощью функции sort ().Все эти способы даже менее эффективны, чем оригинальный способ сделать это.

Может ли в любом случае дать мне более эффективный способ сортировки, чтобы найти my_diff или, возможно, сделать другие части кода более эффективными?Это часть sort (), которая, по-видимому, является неэффективной частью кода.

find_missing <- function(sequence){


  len <- length(sequence)

  if(len > 3){
    my_diff <- as.integer(names(sort(table(diff(sequence)), decreasing = TRUE))[1])

    complete_seq <- seq(sequence[1], sequence[len], my_diff)
  }else{
    differences <- diff(sequence)
    complete_seq_1 <- seq(sequence[1],sequence[len],differences[1])
    complete_seq_2 <- seq(sequence[1],sequence[len],differences[2])
    if(length(complete_seq_1) == 4){
      complete_seq <- complete_seq_1
    }else{
      complete_seq <- complete_seq_2
    }
  }

  complete_seq[!complete_seq %in% sequence]

}

Вот несколько примеров последовательностей для проверки работоспособности кода:

find_missing(c(1,3,5,9,11))
find_missing(c(1,5,7))

Вотнекоторые другие вещи, которые я пробовал вместо сортировки:

1:

library(pracma)
Mode(diff(sequence))

2:

library(dplyr)
(data.frame(diff_1 = diff(sequence)) %>% 
  group_by(diff_1) %>%
  summarise(count = n()) %>%
  ungroup() %>%
  filter(count==max(count)))[1]

3:

MaxTable <- function(sequence, mult = FALSE) {

  differences <- diff(sequence)
  if (!is.factor(differences)) differences <- factor(differences)
  A <- tabulate(differences)
  if (isTRUE(mult)) {
    as.integer(levels(differences)[A == max(A)])
  } 
  else as.integer(levels(differences)[which.max(A)])
}

Answer 1

Вот один из способов сделать это, используя seq.Мы можем создать последовательность от минимального значения в последовательности до максимального значения в последовательности, имеющей длину как length(x) + 1, поскольку в последовательности отсутствует только один член.

find_missing  <- function(x) {
  setdiff(seq(min(x), max(x), length.out = length(x) + 1), x)
}

find_missing(c(1,3,5,9,11))
#[1] 7
find_missing(c(1,5,7))
#[1] 3

Answer 2

На самом деле для этого есть простая формула, которая будет работать, даже если ваш вектор не отсортирован ...

find_missing <- function(x) {
   (length(x) + 1) * (min(x) + max(x))/2 - sum(x)
   }

find_missing(c(1,5,7))
[1] 3

find_missing(c(1,3,5,9,11,13,15))
[1] 7

find_missing(c(2,8,6))
[1] 4

Она основана на том факте, что сумма полных рядов должна бытьсреднее значение умноженное на длину.

Answer 3

Этот подход использует diff() вектора - всегда будет одно различие выше, чем другие.

find_missing <- function(x) {
  diffs <- diff(x)
  x[which.max(diffs)] + min(diffs)
}

find_missing(c(1,3,5,9,11))
[1] 7
find_missing(c(1,5,7))
[1] 3