当前位置：首页 > news >正文

【算法实践】算法面试常见问题——数组的波浪排序

news 来源：原创 2025/9/2 3:53:02

问题描述

给定一个无序整数数组，将其排列成波浪形数组。若数组 arr[0..n-1] 满足以下条件，则称为波浪形：
arr[0] >= arr[1] <= arr[2] >= arr[3] <= arr[4] >= ...
或
arr[0] <= arr[1] >= arr[2] <= arr[3] >= arr[4] <= ...

输入输出示例

示例 1

输入: arr[] = {10, 5, 6, 3, 2, 20, 100, 80}
输出: arr[] = {10, 5, 6, 2, 20, 3, 100, 80}
解释:
输出数组满足 10 >= 5 <= 6 >= 2 <= 20 >= 3 <= 100 >= 80 的波浪形式。
波浪形允许两种交替模式（大-小或小-大交替），只要保持上下交替即可。

示例 2

输入: arr[] = {20, 10, 8, 6, 4, 2}
输出: arr[] = {20, 8, 10, 4, 6, 2}
解释:
输出数组满足 20 >= 8 <= 10 >= 4 <= 6 >= 2 的波浪形式。

关键要求

交替规则：相邻元素必须满足 >= 和 <= 交替出现。
多解性：可能存在多个有效答案（如示例 1 的另一种解为 {5, 10, 2, 6, 3, 20, 80, 100}）。
局部调整：无需全局排序，只需保证局部交替关系。

算法思路（附加说明）

方法 1：排序后交换相邻元素

步骤：
1. 先对数组升序排序。
2. 遍历数组，每两个相邻元素交换一次。
复杂度：
- 时间复杂度：O(n log n)（排序耗时）。
- 空间复杂度：O(1)（原地操作）。

方法 2：单次遍历调整（推荐）

核心思想：
确保所有偶数位置元素大于等于其相邻元素，即可自动满足波浪条件。
步骤：
1. 遍历所有偶数索引位置（i = 0, 2, 4, ...）。
2. 对每个位置 i：
  - 若 arr[i-1] > arr[i]（且 i > 0），交换它们。
  - 若 arr[i+1] > arr[i]（且 i < n-1），交换它们。
复杂度：
- 时间复杂度：O(n)（单次遍历）。
- 空间复杂度：O(1)（原地操作）。

Java实现

/*** 将无序数组排列成"波浪形"数组：* 满足 arr[0] >= arr[1] <= arr[2] >= arr[3]...* 或 arr[0] <= arr[1] >= arr[2] <= arr[3]...*/public class WaveArraySorter {/*** 交换数组中两个元素的位置* @param arr 目标数组* @param i 第一个元素的索引* @param j 第二个元素的索引*/private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}/*** O(n)时间复杂度实现波浪排序的核心算法* 关键思想：确保所有偶数索引元素都大于相邻元素*/public static void sortWave(int[] arr) {// 遍历所有偶数索引位置（0,2,4...）for (int i = 0; i < arr.length; i += 2) {           // 如果前一个元素更大，交换它们if (i > 0 && arr[i-1] > arr[i]) {swap(arr, i-1, i);}// 如果后一个元素更大，交换它们if (i < arr.length-1 && arr[i+1] > arr[i]) {swap(arr, i, i+1);}}}public static void main(String[] args) {// 测试用例1int[] arr1 = {10, 5, 6, 3, 2, 20, 100, 80};System.out.println("原始数组1：" + Arrays.toString(arr1));sortWave(arr1);System.out.println("波浪排序1：" + Arrays.toString(arr1));// 测试用例2int[] arr2 = {20, 10, 8, 6, 4, 2};System.out.println("\n原始数组2：" + Arrays.toString(arr2));sortWave(arr2);System.out.println("波浪排序2：" + Arrays.toString(arr2));}
}

【算法实践】算法面试常见问题——数组的波浪排序

问题描述给定一个无序整数数组，将其排列成波浪形数组。若数组 arr[0..n-1] 满足以下条件，则称为波浪形： arr[0] > arr[1] < arr[2] > arr[3] < arr[4] > ... 或 arr[0] < arr[1] > arr[2] < arr[3] > arr[4] &l…...

编程日记 2025/9/2 3:53:02

【大模型深度学习】如何估算大模型需要的显存

一、模型参数量参数量的单位参数量指的是模型中所有权重和偏置的数量总和。在大模型中，参数量的单位通常以“百万”（M）或“亿”（B，也常说十亿）来表示。百万（M）：表示…...

编程日记 2025/9/2 3:46:05

[论文阅读]PMC-LLaMA: Towards Building Open-source Language Models for Medicine

PMC-LLaMA：构建医学开源语言模型摘要最近，大语言模型在自然语言理解方面展现了非凡的能力。尽管在日常交流和问答场景下表现很好，但是由于缺乏特定领域的知识，这些模型在需要精确度的领域经常表现不佳，例如医学应用…...

编程日记 2025/8/27 6:27:26

`use_tempaddr` 和 `temp_valid_lft ` 和 `temp_prefered_lft ` 笔记250405

use_tempaddr 和 temp_valid_lft 和 temp_prefered_lft 笔记250405 以下是 Linux 系统中与 IPv6 临时隐私地址相关的三个关键参数 use_tempaddr、temp_valid_lft 和 temp_prefered_lft 的详细说明及协作关系： 📜 参数定义与功能参数作用默认值依赖关…...

编程日记 2025/9/1 9:08:48

如何设置 JVM 内存参数（-Xms、-Xmx、-Xss 等）？

JVM 内存参数用于控制 Java 虚拟机使用的内存大小和行为。以下是一些常用的 JVM 内存参数及其设置方法： 1. 堆内存 (Heap Memory): -Xms<size>: 设置 JVM 初始堆大小 (initial heap size)。例如：-Xms2g (初始堆大小为 2GB)默认值：物…...

编程日记 2025/9/2 3:49:44

【MATLAB TCP/IP客户端与NetAssist上位机双向通信实战指南】

MATLAB TCP/IP客户端与NetAssist上位机双向通信实战指南一、前言在工业控制和数据采集领域，TCP/IP通信是最常用的网络通信协议之一。MATLAB作为强大的科学计算软件，与各种上位机软件(如NetAssist)进行通信可以实现数据采集、设备控制和实时监控等功能…...

编程日记 2025/9/1 10:46:28

联合、枚举、类型别名

数据类型： 已学--整数、实数、字符、字符串、数组、指针、结构待学--向量（vector）类型：优于数组非主流的类型--联合（union）、枚举（enum） 一、联合联合类似于结构，可以容…...

编程日记 2025/9/2 3:49:44

Array 和 ArrayList 有何区别？什么时候更适合用 Array？

面试官提问： 你能简要说明 Array 和 ArrayList 之间的主要区别吗？在什么场景下更适合使用 Array？ 标准回答： 在 Java 中，Array（数组）和 ArrayList（动态数组）都可以用于存…...

编程日记 2025/9/1 6:33:58

对状态模式的理解

对状态模式的理解一、场景二、不采用状态模式1、代码2、缺点三、采用状态模式1、代码1.1 状态类1.2 上下文（这里指：媒体播放器）1.3 客户端 2、优点一、场景同一个东西（例如：媒体播放器），有一…...

编程日记 2025/9/2 3:52:05

【学Rust写CAD】31 muldiv255函数（muldiv255.rs）

源码 // Calculates floor(a*b/255 0.5) #[inline] pub fn muldiv255(a: u32, b: u32) -> u32 {// The deriviation for this formula can be// found in "Three Wrongs Make a Right" by Jim Blinn.let tmp a * b 128;(tmp (tmp >> 8)) >> 8 }代…...

编程日记 2025/9/1 16:42:27

使用VSCode编写C#程序

目录一、环境搭建：构建高效开发基础1. 安装VSCode2. 配置.NET SDK3. 安装核心扩展二、项目开发全流程1. 创建项目2. 代码编辑技巧3. 调试配置4. 高级调试技巧5. 编译与运行三、常见问题解决指南1. 项目加载失败2. IntelliSense失效3. 代码格式化4. 典型编译错误&…...

编程日记 2025/8/28 4:07:30

chromadb

chromadb是一个轻量化的向量数据库，可以和llama-index等RAG框架使用。底层基于sqllite。 Getting Started - Chroma Docs 1、安装 $pip install chromadb pip install chromadb-client --在CS模式下，如果机器A上只需要安装客户端 2、可以使用客户端…...

编程日记 2025/9/1 18:46:28

第十章: 可观测性_《凤凰架构：构建可靠的大型分布式系统》

第十章: 可观测性可观测性是现代分布式系统监控和故障排查的核心能力。本章从事件日志、链路追踪、聚合度量三个维度构建完整的可观测性体系，以下是各部分的重点解析与实践要点： 一、事件日志（Event Logging） 1. 核心目标全链…...

编程日记 2025/9/1 6:11:31

vscode和cursor对ubuntu22.04的remote ssh和X-Windows的无密码登录

这里写自定义目录标题写在前面需求的描述问题的引出昨天已使能自动登录上午我的改变UBUNTU 22.04关闭密码规则一：修改 /etc/pam.d/common-password 文件二：修改 /etc/security/pwquality.conf 文件方法三：禁用 pam_pwquality.so 模块 vscod…...

编程日记 2025/9/2 3:51:18

Mlivus Cloud SDK v2的革新：性能优化与实战解析

作为大禹智库的向量数据库高级研究员王帅旭，我在过去30多年的AI应用实战中见证了向量数据库技术的演进历程。今天，我将从专业角度深入剖析Mlivus Cloud SDK v2的架构革新，特别是针对性能瓶颈问题的突破性解决方案。本文不仅会详细解析技术原理，还将提供可操作的优化建议，帮…...

编程日记 2025/9/2 3:47:28

stl_list的模拟实现

文章目录 stl_list的模拟实现迭代器的介绍以及分类stl_list的基本接口介绍stl_list的模拟实现结点类迭代器类基本迭代器操作链表类链表基本操作结语我们今天又见面啦，给生活加点impetus！！开启今天的编程之路作者：٩( ‘ω’ …...

编程日记 2025/9/1 9:42:45

【蓝桥杯】十五届省赛B组c++

目录前言握手问题分析排列组合写法枚举小球反弹分析代码好数分析代码 R 格式分析代码宝石组合分析代码数字接龙分析代码拔河分析代码总结前言主播这两天做了一套蓝桥杯的省赛题目（切实感受到了自己有多菜&#x…...

编程日记 2025/9/1 15:58:28

变分自编码器（VAE）概念解析与用法实例：根据原图像生成新图像

目录 1. 前言 2. VAE原理 2.1 什么是VAE？ 2.2 编码器（Encoder） 2.3 重参数化技巧（Reparameterization Trick） 2.4 解码器（Decoder） 2.5 损失函数 3. Pytorch实现：根据原图像…...

编程日记 2025/9/1 10:49:05

AI随身翻译设备：从翻译工具到智能生活伴侣

文章目录 AI随身翻译设备的核心功能1. 实时翻译2. 翻译策略3. 翻译流程4. 输出格式二、AI随身翻译设备的扩展功能1. 语言学习助手2. 旅行助手3. 商务助手4. 教育助手5. 健康助手6. 社交助手7. 技术助手8. 生活助手9. 娱乐助手10. 应急助手三、总结四、未来发展趋势&#xff0…...

编程日记 2025/9/1 16:07:33

基于大模型的重症肌无力的全周期手术管理技术方案

目录技术方案文档1. 数据预处理模块2. 多任务预测模型架构3. 动态风险预测引擎4. 手术方案优化系统5. 技术验证模块6. 系统集成架构7. 核心算法清单8. 关键流程图详述实施路线图技术方案文档 1. 数据预处理模块流程图 [输入原始数据] → [联邦学习节点数据对齐] → [多模态特…...

编程日记 2025/9/1 11:09:26

Linux常用命令详解：从基础到进阶

目录一、引言二、文件处理相关命令 （一）grep指令 （二）zip/unzip指令编辑 （三）tar指令 （四）find指令三、系统管理相关命令 （一）shutdown指…...

编程日记 2025/9/1 22:38:18

【全球首发】DeepSeek谷歌版1.1.5 - 免费GPT-4级别AI工具

【全球首发】DeepSeek谷歌版1.1.5 - 免费GPT-4级别AI工具资源简介 DeepSeek谷歌版1.1.5是目前全球领先的免费AI助手，性能超越国内主流AI产品，提供类似GPT-4的智能体验。版本信息最新版本：1.1.5（2024最新版）应用…...

编程日记 2025/9/2 3:49:47

JWT认证服务

JSON Web Token（JWT）是一种用于在网络应用间安全地传递信息的紧凑、自包含的方式。以下是关于 JWT 认证服务器更详细的介绍，包括其意义、作用、工作原理、组成部分、时效性相关内容、搭建条件以及代码案例。 JWT 的意义与作用意义&#xf…...

编程日记 2025/9/2 3:08:01

Raft算法

Raft算法用于保证分布式环境下多节点数据的一致性。原理 Raft算法的主要思想是一个选主(leader selection) 的算法思想，集群种每个节点都有可能成为三种角色。三种角色 leader 对客户端通信的入口，对内数据同步的发起者，一个集群通常只…...

编程日记 2025/9/1 16:57:00

Kotlin 类委托深入解析：以 MMKV 为例看委托机制在 Android 中的巧妙应用

Kotlin 中的类委托（class delegation）是一个非常实用的特性，它允许我们将接口的实现交给另一个对象，从而简化代码，提升复用性和灵活性。本文将通过简单的 Demo 介绍类委托的基本用法，并以 Android 中的 MMK…...

编程日记 2025/9/1 18:03:43

2025年渗透测试面试题总结-某一线实验室实习扩展（题目+回答）

网络安全领域各种资源，学习文档，以及工具分享、前沿信息分享、POC、EXP分享。不定期分享各种好玩的项目及好用的工具，欢迎关注。目录某一线实验室实习扩展一、流量分析深度实践 1. FTP反弹定时确认包流量检测 1.1 攻击原理与特征 1.…...

编程日记 2025/8/31 11:25:15

2025大唐杯仿真3——移动性管理

仅仅是1-2之间的信息交互...

编程日记 2025/9/1 22:48:29

云原生与微服务的关系

云原生（Cloud Native）和微服务（Microservices）是现代软件开发和部署中密切相关的两个概念，它们共同推动了应用程序的架构设计、开发模式和运维方式的变革。以下是两者的关系及核心要点： 定义与核心概念云原…...

编程日记 2025/9/1 7:11:52

【百日精通JAVA | SQL篇 | 第三篇】 MYSQL增删改查

SQL得最核心就是增删改查一个后端开发，在工作中，最常见的场景就是CRUD。插入数据 insert into student values (1,zhangsan); 指定列插入数据同时多个列明之间使用逗号，来分割 insert into student (name) values (zhaoliu); 这个黑框…...

编程日记 2025/8/31 11:28:01

【leetcode】记录与查找：哈希表的题型分析

前言 🌟🌟本期讲解关于力扣的几篇题解的详细介绍~~~ 🌈感兴趣的小伙伴看一看小编主页：GGBondlctrl-CSDN博客 🔥 你的点赞就是小编不断更新的最大动力 🎆那么废话不…...

编程日记 2025/8/30 20:09:53

如何在 Windows 10 上安装 PyGame

PyGame 是 Python 编程语言中的一组跨平台模块，这意味着您可以在任何操作系统上安装它，这篇文章告诉您如何在 Windows 10 上安装 PyGame。如何在 Windows 10 上安装 PyGame？ PyGame 依赖于 Python，这意味着您必须在安装 PyGame …...

编程日记 2025/9/1 5:57:21

LVGL修改标签文本，GUI Guider的ui不生效

一.问题背景笔者最近在学习LVGL框架，同时准备使用该框架作为课程设计的一部分，于是需要从静态显示进阶到动态显示以及事件交互。一方面由于笔者是初次接触LVGL，对它并不熟悉，另一方面由于其网络上的针对性具体资料太少&a…...

编程日记 2025/8/30 18:14:10

制造装备物联及生产管理ERP系统设计与实现(代码+数据库+LW)

摘要传统办法管理信息首先需要花费的时间比较多，其次数据出错率比较高，而且对错误的数据进行更改也比较困难，最后，检索数据费事费力。因此，在计算机上安装制造装备物联及生产管理ERP系统软件来发挥其高效地信息处理…...

编程日记 2025/8/30 0:58:34

PowerPhotos：拯救你的Mac照片库，告别苹果原生应用的局限

如果你用Mac管理照片，大概率被苹果原生「照片」应用折磨过——无法真正并行操作多个图库。每次切换图库都要关闭重启，想合并照片得手动导出导入，重复文件更是无处可逃…… 直到我发现了 PowerPhotos，这款专为Mac设计的照片库管理…...

编程日记 2025/8/31 11:30:22

软件工程面试题（三十）

将ISO8859-1字符串转成GB2312编码，语句为？ String snew String(text.getBytes(“iso8859-1”),”gb2312”). 说出你用过的J2EE标准的WEB框架和他们之间的比较？ 答：用过的J2EE标准主要有：JSP&Servlet、JDBC、JNDI…...

编程日记 2025/8/31 19:18:29

Java面试黄金宝典35

1. A 和 B 两个表做等值连接 (Inner join) 怎么优化索引优化：在连接字段上创建索引，让数据库在进行等值连接时，能够快速定位匹配的记录，减少全表扫描的开销。例如，若 A 表和 B 表通过 id 字段进行连接，可在…...

编程日记 2025/9/1 21:03:32

openssl-1.0.1e.tar.gz编译安装步骤

下载与验证 openssl-1.0.1e.tar.gz下载链接：https://pan.quark.cn/s/d682551565e8 校验文件完整性（示例）： # 检查 SHA256 哈希值 sha256sum openssl-1.0.1e.tar.gz # 对比官方发布的哈希值（需从 OpenSSL 官网获取&a…...

编程日记 2025/8/30 0:41:02

供应链业务-供应链全局观（二）

概述我们在供应链业务知识分享的第一篇供应链业务-供应链全局观（一）中大致聊了以下三点： 1、供应链的本质：环环相扣的增值网络。供应链是从供应商的供应商到客户的客户之间，通过采购、生产、运输、仓储、销售等环节…...

编程日记 2025/9/1 22:49:06

在 Flutter 中Navigator.push 用于实现页面之间的导航

在 Flutter 中，Navigator.push 是一个非常重要的方法，用于实现页面之间的导航。通过 Navigator.push，你可以将一个新的页面（路由）推送到导航栈中，从而显示新的内容。以下是一个详细的教程，帮助…...

编程日记 2025/9/1 21:29:16

安永启用AI驱动SAP云ERP系统

安永（EY）宣布与 SAP 和微软展开战略合作，正式启动将其内部业务系统升级为基于 SAP S/4HANA Cloud 私有版的现代化 ERP 系统，并部署在 Microsoft Azure 云平台上。此次转型不仅涉及系统更新，还将通过引入人工智能&#…...

编程日记 2025/8/31 10:05:02

Augment Code：下一代AI编程助手，能否超越GitHub Copilot？

1. 背景介绍近日，AI编程助手公司 Augment Code 宣布完成 2.27亿美元B轮融资，估值接近 9.77亿美元，距离独角兽企业仅一步之遥。本轮融资由 Sutter Hill Ventures、Index Ventures、Innovation Endeavors、Lightspeed Venture Partners 和 Me…...

编程日记 2025/9/1 7:00:44

图像处理之《直方图规定化和低失真数据隐藏的可逆对比度增强》论文阅读

全文目录一、文章摘要二、直方图规定化三、提出的方法A.峰值和零点的选择B.数据序列扩展C. V L D E \mathrm{VLD_E} VLDE: 带有扩展的极低失真D.提出的RCE-HS方案四、实现细节五、汇报PPT一、文章摘要本文研究可逆对比度增强(RCE)。图像增强是通过直方图规定化实现的，直方…...

编程日记 2025/8/28 3:54:59

状态模式~

状态模式在软件系统中,有些对象也像水一样具有多种状态,这些状态在某些情况下能够相互转换,而且对象在不同状态下也将具有不同的行为. 状态模式(state pattern)的定义: 允许一个对象在其内部状态改变时改变它的行为。对象看起来似乎修改了它的类。状态模式就是用于解决系统…...

编程日记 2025/8/31 0:56:28

Latex入门之超详细的Latex环境配置教程

最近在学习Latex，顺便给大家分享一下Latex环境配置的心得。Latex作为一种高质量的排版系统，广泛应用于学术论文、书籍和报告的排版中。对于初学者来说，配置Latex环境可能是个挑战，但只要按照本文的步骤来，其实并不难。…...

编程日记 2025/8/31 22:47:46

[WUSTCTF2020]CV Maker1

进来是个华丽的界面，我们先跟随这个网页创造一个用户发现了一个上传端口，尝试上传一个php文件并抓包直接上传进不去，加个GIF89A uploads/d41d8cd98f00b204e9800998ecf8427e.php 传入并且报告了上传路径，然后使用蚁剑连接...

编程日记 2025/8/18 0:41:52

第1课：React开发环境搭建与第一个组件

第1课：React开发环境搭建与第一个组件学习目标搭建React开发环境创建第一个React项目了解项目基本结构编写并运行第一个React组件一、环境准备 1. 安装Node.js React开发需要Node.js环境，它包含了npm（Node Package Manager&#xff0…...

编程日记 2025/8/28 17:20:13

go垃圾回收机制

Go语言的垃圾回收（GC）机制旨在高效管理内存，同时最小化对程序性能的影响。其核心设计结合了并发标记清除、三色标记法和写屏障技术，显著减少了停顿时间（Stop-The-World, STW）。以下是Go垃圾回收机制的关键特…...

编程日记 2025/8/24 13:02:52

【GPT入门】第 34 课：深度剖析 ReAct Agent 工作原理及代码实现

【GPT入门】第 34 课：深度剖析 ReAct Agent 工作原理及代码实现 1. React Agent概述2. React Agent工作原理、关键特点、应用场景3. langchain的ReAct Agent代码实现3.1 Openai1.x 代码实现3.2 Openai 0.x的实现3.3 新旧版API异同比较 1. React Agent概述定义与基…...

编程日记 2025/8/30 10:26:26

MySQL介绍及使用

1. 安装、启动、配置 MySQL 1. 安装 MySQL 更新软件包索引 sudo apt update 安装 MySQL 服务器 sudo apt install mysql-server 安装过程中可能会提示你设置 root 用户密码。如果没有提示，可以跳过，后续可以手动设置。 2. 配置 MySQL 运行安全脚本…...

编程日记 2025/8/27 15:38:06

九、重学C++—类和函数

上一章节： 八、重学C—动态多态（运行期）-CSDN博客https://blog.csdn.net/weixin_36323170/article/details/147004745?spm1001.2014.3001.5502 本章节代码： cpp/cppClassAndFunc.cpp CuiQingCheng/cppstudy - 码云 - 开源中国…...

编程日记 2025/8/28 16:36:41