LeetCode中级算法-排序和搜索(1)

作者:神秘网友 发布时间:2021-01-12 20:21:48

LeetCode中级算法-排序和搜索(1)

颜色分类

[题目]

给定一个包含红色、白色和蓝色,一共 n 个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。此题中,我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

[输入1]

nums = [2,0,1]

[返回1]

[0,1,2]

[输入2]

nums = [2,0,2,1,1,0]

[返回2]

[0,0,1,1,2,2]

[解法1]

使用一个指针,遍历两遍数组,第一遍遍历将数组中所有的0交换到数组的开头,记录一个targetIndex为当前替换到了哪个位置,第二遍遍历的时候,从上一次的targetIndex开始,将数组中所有的1从这个位置开始交换

[代码实现1]

func computeResult(input []int) []int {
  // 首先将所有的0交换到最前面
  targetIndex, input := _compute(input, 0, 0)
  // 然后将1接着targetIndex放置
  _, input = _compute(input, 1, targetIndex)
  return input
}

func _compute(input []int, target int, targetIndex int) (int, []int) {
  for i := 0; i  len(input); i++ {
    if input[i] == target {
      input[i], input[targetIndex] = input[targetIndex], input[i]
      targetIndex++
    }
  }

  return targetIndex, input
}

[解法2]

使用两个指针,分别遍历0和2的元素,将0交换到数组的开头位置,将2交换到数组结尾的位置

[代码实现2]

func computeResult2(input []int) []int {
  targetStartIndex := 0
  targetEndIndex := len(input) - 1
  for i := 0; i  len(input); i++ {
    if input[i] == 0 {
      input[i], input[targetStartIndex] = input[targetStartIndex], input[i]
      targetStartIndex++
    } else if input[i] == 2 {
      input[i], input[targetEndIndex] = input[targetEndIndex], input[i]
      targetEndIndex--
    }
  }

  return input
}

[代码测试]

package main

import fmt

func main() {
  //input := []int {2,0,2,1,1,0}
  input := []int {2, 0, 1}
  result := computeResult(input)
  fmt.Println(result:, result)

  result2 := computeResult2(input)
  fmt.Println(result2:, result2)
}

前 K 个高频元素

[题目]

给定一个非空的整数数组,返回其中出现频率前 k 高的元素。

[输入1]

nums = [1,1,1,2,2,3], k = 2

[返回1]

[1,2]

[输入2]

nums = [1], k = 1

[返回2]

[1]

[解法]

首先遍历一遍数组,按照key-value存储每个元素出现的次数,key为元素,value是该元素出现的次数,遍历完成之后,建立一个小顶堆,golang中小顶堆的建立可以使用heap.Init,遍历元素出现次数的map,将[key, value]的数组加入到小顶堆中,当小顶堆中元素超过k的时候,就弹出堆顶的元素,直到将整个map遍历完毕

[代码实现]

package main

import (
  container/heap
  fmt
)

func main() {
  input := []int {1,1,1,2,2,3}
  result := computeResult(input, 2)
  fmt.Println(result:, result)
}

func computeResult(input []int, k int) []int {
  filter := map[int]int {}
  for i := 0; i  len(input); i++ {
    if _, exists := filter[input[i]]; exists {
      filter[input[i]] += 1
    } else {
      filter[input[i]] = 1
    }
  }

  h := IHeap{}
  heap.Init(h)
  for key, value := range filter  {
    heap.Push(h, [2]int{key, value})
    if h.Len()  k {
      heap.Pop(h)
    }
  }

  result := make([]int, k)
  // 小顶堆是最小的在最上面,最先被Pop出来
  for i := 0; i  k; i++ {
    result[k - i - 1] = heap.Pop(h).([2]int)[0]
  }

  return result
}

type IHeap struct {
  items [][2]int
}

func (h *IHeap) Push(x interface{}) {
  h.items = append(h.items, x.([2]int))
}

func (h *IHeap) Len() int {
  return len(h.items)
}

// 构建小顶堆
func (h *IHeap) Less(i, j int) bool {
  return h.items[i][1]  h.items[j][1]
}

func (h *IHeap) Swap(i, j int) {
  h.items[i], h.items[j] = h.items[j], h.items[i]
}

func (h *IHeap) Pop() interface{} {
  n := h.Len()
  item := h.items[n - 1]
  h.items = h.items[0: n - 1]
  return item
}

寻找峰值

[题目]

给定一个非空的整数数组,返回其中出现频率前 k 高的元素。

[输入1]

nums = [1,2,3,1]

[返回1]

2

[输入2]

nums = [1,2,1,3,5,6,4]

[返回2]

1 或 5

[解法]

因为题目中只需要返回一个,那么我们可以使用类似二叉树遍历,需要注意下面都是mid + 1,这是因为整数除以2,会向下取整,e.g. (2 + 3) / 2 = 2。算法的复杂度为O(logn)

[代码实现]

package main

import fmt

func main() {
    input := []int {1,2,1,3,5,6,4}
    result := computeResult(input)
    fmt.Println(result:, result)
}

func computeResult(input []int) int {
    left := 0
    right := len(input) - 1
    for left  right {
        mid := (left + right) / 2
        if input[mid]  input[mid + 1] {
            right = mid
        } else {
            left = mid + 1
        }
    }

    return left
}

在排序数组中查找元素的第一个和最后一个位置

[题目]

给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

[输入1]

nums = [5,7,7,8,8,10], target = 8

[返回1]

[3,4]

[输入2]

nums = [5,7,7,8,8,10], target = 6

[返回2]

[-1,-1]

[解法]

排序好的数组,使用二分查找,向前计算开头元素的下标。注意计算尾部下标的时候,可以计算target + 1元素的首个下标,这个下标减去1,就是target尾部下标

[代码实现]

package main

import fmt

func main() {
  input := []int {5,7,7,8,8,10}
  target := 8
  result := computeResult(target, input)
  fmt.Println(result:, result)
}

func computeResult(target int, input []int) []int {
  before := beforeIndex(target, input)
  after := beforeIndex(target + 1, input)
  if after == -1 {
    after = before
  }
  return []int { before, after }
}

func beforeIndex(target int, input []int) int {
  left := 0
  right := len(input) - 1
  for left  right  {
    mid := (left + right) / 2
    if target == input[mid] {
      return mid
    } else if target  input[mid] {
      left = mid + 1
    } else {
      right = mid + 1
    }
  }

  return -1
}

LeetCode中级算法-排序和搜索(1) 相关文章

  1. LeetCode中级算法-动态规划

    跳跃游戏 [题目] 给定一个非负整数数组,你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个位置。 [输入1] [2,3,1,1,4] [返回1] true 解释: 我们可以先跳 1 步,从位置 0 到达 位置 1, 然后再从位

  2. LeetCode中级算法-数学(1)

    快乐数 [题目] 编写一个算法来判断一个数 n 是不是快乐数。 「快乐数」定义为:对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和,然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。如果 可以变为 1,那么这个数就是快乐

  3. Angel图神经网络算法在推荐场景下的实践

    分享嘉宾:孙瑞鸿?腾讯大数据 编辑整理:赵文娇 出品平台:DataFunTalk、AI启蒙者 导读: 随着数据多样性的发展,图计算已经成为业界的一个重要的研究方向,其中图神经网络广泛应用于图的表征学习,与传统的图学习相比,既能学习图网络的拓扑结构,也能聚合

  4. 贪心算法:我要监控二叉树!

    一路跟着「代码随想录」刷题的录友们,二叉树是不是都快忘了,哈哈,反正我讲过的内容我就默认大家都会了,来来来,本题是二叉树上的贪心。需要重温二叉树的录友,传送门: leetcode刷题最强指南(版本1.0) 通知: 一些录友表示经常看不到每天的文章,现在

  5. LeetCode中级算法-数学(2)

    Pow(x, n) [题目] 实现 pow(x, n) ,即计算 x 的 n 次幂函数。 [输入1] 2.00000, 10 [返回1] 1024.00000 [输入2] 2.10000, 3 [返回2] 9.26100 [输入3] 2.00000, -2 [返回3] 0.25000 [解法] 无 [代码实现] package mainimport fmtfunc main() { input := floa

  6. Angel推荐算法在游戏推荐中的应用

    文章作者:王培军?腾讯 高级工程师 整理编辑:李沛欣 出品平台:DataFunTalk、AI启蒙者 导读: Angel是腾讯自研的分布式高性能的机器学习平台,支持机器学习、深度学习、图计算以及联邦学习等场景。Angel的深度学习平台已应用在腾讯的很多个场景中。本次分享

  7. 计算机算法的五个特性是什么

    计算机算法的五个特性是:1、有穷性,算法必须能在执行有限个步骤之后终止;2、确切性,算法的每一步骤必须有确切的定义;3、输入项,一个算法有0个或多个输入;4、输出项,一个算法有一个或多个输出;5、可行性,每个计算步骤都可以在有限时间内完成。 算法

  8. 一个算法示例:PHP实现开心消消乐

    本文主要介绍了关于PHP如何实现我们大家都知道的开心消消乐的算法。 推荐:《PHP视频教程》 一、需求描述: 1、在一个8*8的矩阵方格中随机出现5种颜色的色块。 2、当有三个或以上色块在横向或纵向上相连,则消除这些色块。 3、色块消除后,上方色块往下平移,

  9. LRU算法的实现

    缘由:看到redis的缓存淘汰机制,便自己实现了一下 代码实现(双向链表+HashMap) package com.jarjune.jdalao.framework.algorithm;import java.util.*;/** * LRU * @author jarjune * @version 1.0.1 * @date 2020/11/19 */public class LRUCacheK, V { //

  10. 拉斯维加斯算法之n后问题

    1、拉斯维加斯(Las Vegas)算法 舍伍德算法优点在于计算时间复杂度对所有实例相对均匀,但与其相应的确定性算法相比,其平均时间复杂度没有改进。拉斯维加斯算法则不然,它能显著改进算法的有效性,甚至对某些迄今为止找不到有效算法的问题,也能得到满意的算

每天更新java,php,javaScript,go,python,nodejs,vue,android,mysql等相关技术教程,教程由网友分享而来,欢迎大家分享IT技术教程到本站,帮助自己同时也帮助他人!

Copyright 2020, All Rights Reserved. Powered by 跳墙网(www.tqwba.com)|网站地图|关键词