草庐IT

java - 给定一个数组 [a1b2c3d4] 转换为 [abcd1234]

coder 2023-08-30 原文

约束:

  1. O(1) 空间
  2. O(n) 时间

这不是作业题，只是我遇到的一个有趣的问题。

这里有一些我能想到的解决方案，但在给定的限制条件下没有任何解决方案。

方法一

*O(n) 内存*

  • 递归地将数组分成两部分。 (继续划分直到每个子问题的大小 <=2>
  • 对每个子问题进行排序，数组在前，数字在后。
  • 合并子问题数组

方法二

在 O(n log n) 时间内

  • 根据字典顺序对数组进行排序，它变为 1234abcd
  • 反转数组 4321dcba 的两半
  • 反转整个字符串abcd1234

方法三

如果定义了数字范围

此外，如果情况是数字在特定范围内，那么我可以初始化一个 int say track= 0; 当我遇到数组中的数字时设置适当的位 例如 (1 < a[2]="" )="" 。="" 1.="" 将字母交换到数组的前半部分="" 2.在track变量中标记数字="" 3.="">

方法四 如果我们想移除整数范围的约束，我们可以使用方法 3 和 HashMap，但这样会需要更多的内存。

想不出更好的方法来解决 O(1) 时间和 O(n) 空间的泛型问题。

这里的通用问题是指:

给定一个序列 x1y1x2y2x3y3....xnyn 其中 x1 , x2 是字母表 x1 < x2=""><....>< xn="" 和="" y1y2...yn="" 是整数。="" y1="">< y2=""><....>< yn="" 将输出排列为="">

有什么建议吗？

最佳答案

什么是n？假设 n 是输入的大小:

这称为列表的卷积。本质上，您必须将一对列表 (a,1),(b,2),(c,3),(d,4) 转换为一对列表 ( a,b,c,d),(1,2,3,4)。这与矩阵的转置操作相同。

无论如何，你必须将结构视为一个 k 维数组，其中 k = lg n。数组的卷积是将索引 i 处的值“移动”到按位旋转的索引 i 时得到的结果。在这种情况下，我们希望将索引向右旋转 1 位。这意味着卷积是一个最大循环长度为 k 的排列。诀窍是从每个循环中选择一个索引——这将始终包括 0 和 n-1。

编辑:实际上，您可能想要的是将排列分解为转置的乘积。然后，您需要做的就是交换。

关于java - 给定一个数组 [a1b2c3d4] 转换为 [abcd1234]，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12683749/

给定a1b2c3d4strongsectionlijavaarraysalgorithmarray-algorithms

有关java - 给定一个数组 [a1b2c3d4] 转换为 [abcd1234]的更多相关文章

  1. java - 等价于 Java 中的 Ruby Hash - 2

    我真的很习惯使用Ruby编写以下代码:my_hash={}my_hash['test']=1Java中对应的数据结构是什么？ 最佳答案 HashMapmap=newHashMap();map.put("test",1);我假设？ 关于java-等价于Java中的RubyHash，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/22737685/

  2. java - 从 JRuby 调用 Java 类的问题 - 2

    我正在尝试使用boilerpipe来自JRuby。我看过guide从JRuby调用Java，并成功地将它与另一个Java包一起使用，但无法弄清楚为什么同样的东西不能用于boilerpipe。我正在尝试基本上从JRuby中执行与此Java等效的操作:URLurl=newURL("http://www.example.com/some-location/index.html");Stringtext=ArticleExtractor.INSTANCE.getText(url);在JRuby中试过这个:require'java'url=java.net.URL.new("http://www

  3. java - 我的模型类或其他类中应该有逻辑吗 - 2

    我只想对我一直在思考的这个问题有其他意见，例如我有classuser_controller和classuserclassUserattr_accessor:name,:usernameendclassUserController//dosomethingaboutanythingaboutusersend问题是我的User类中是否应该有逻辑user=User.newuser.do_something(user1)oritshouldbeuser_controller=UserController.newuser_controller.do_something(user1,user2)我

  4. java - 什么相当于 ruby​​ 的 rack 或 python 的 Java wsgi？ - 2

    什么是ruby​​的rack或python的Java的wsgi？还有一个路由库。 最佳答案 来自Python标准PEP333:Bycontrast,althoughJavahasjustasmanywebapplicationframeworksavailable,Java's"servlet"APImakesitpossibleforapplicationswrittenwithanyJavawebapplicationframeworktoruninanywebserverthatsupportstheservletAPI.ht

  5. 世界前沿3D开发引擎HOOPS全面讲解——集3D数据读取、3D图形渲染、3D数据发布于一体的全新3D应用开发工具 - 2

    无论您是想搭建桌面端、WEB端或者移动端APP应用，HOOPSPlatform组件都可以为您提供弹性的3D集成架构，同时，由工业领域3D技术专家组成的HOOPS技术团队也能为您提供技术支持服务。如果您的客户期望有一种在多个平台（桌面/WEB/APP，而且某些客户端是“瘦”客户端）快速、方便地将数据接入到3D应用系统的解决方案，并且当访问数据时，在各个平台上的性能和用户体验保持一致，HOOPSPlatform将帮助您完成。利用HOOPSPlatform，您可以开发在任何环境下的3D基础应用架构。HOOPSPlatform可以帮您打造3D创新型产品，HOOPSSDK包含的技术有：快速且准确的CAD

  6. FOHEART H1数据手套驱动Optitrack光学动捕双手运动(Unity3D) - 2

    本教程将在Unity3D中混合Optitrack与数据手套的数据流，在人体运动的基础上，添加双手手指部分的运动。双手手背的角度仍由Optitrack提供，数据手套提供双手手指的角度。 01  客户端软件分别安装MotiveBody与MotionVenus并校准人体与数据手套。MotiveBodyMotionVenus数据手套使用、校准流程参照：https://gitee.com/foheart_1/foheart-h1-data-summary.git02  数据转发打开MotiveBody软件的Streaming，开始向Unity3D广播数据；MotionVenus中设置->选项选择Unit

  7. Observability：从零开始创建 Java 微服务并监控它 （二） - 2

    这篇文章是继上一篇文章“Observability：从零开始创建Java微服务并监控它（一）”的续篇。在上一篇文章中，我们讲述了如何创建一个Javaweb应用，并使用Filebeat来收集应用所生成的日志。在今天的文章中，我来详述如何收集应用的指标，使用APM来监控应用并监督web服务的在线情况。源码可以在地址 https://github.com/liu-xiao-guo/java_observability 进行下载。摄入指标指标被视为可以随时更改的时间点值。当前请求的数量可以改变任何毫秒。你可能有1000个请求的峰值，然后一切都回到一个请求。这也意味着这些指标可能不准确，你还想提取最小/

  8. 【Java 面试合集】HashMap中为什么引入红黑树，而不是AVL树呢 - 2

    HashMap中为什么引入红黑树，而不是AVL树呢1.概述开始学习这个知识点之前我们需要知道，在JDK1.8以及之前，针对HashMap有什么不同。JDK1.7的时候，HashMap的底层实现是数组+链表JDK1.8的时候，HashMap的底层实现是数组+链表+红黑树我们要思考一个问题，为什么要从链表转为红黑树呢。首先先让我们了解下链表有什么不好？？？2.链表上述的截图其实就是链表的结构，我们来看下链表的增删改查的时间复杂度增：因为链表不是线性结构，所以每次添加的时候，只需要移动一个节点，所以可以理解为复杂度是N(1)删：算法时间复杂度跟增保持一致查：既然是非线性结构，所以查询某一个节点的时候

  9. Unity 3D 制作开关门动画,旋转门制作,推拉门制作,门把手动画制作 - 2

    Unity自动旋转动画1.开门需要门把手先动,门再动2.关门需要门先动,门把手再动3.中途播放过程中不可以再次进行操作觉得太复杂?查看我的文章开关门简易进阶版效果:如果这个门可以直接打开的话,就不需要放置"门把手"如果门把手还有钥匙需要旋转,那就可以把钥匙放在门把手的"门把手",理论上是可以无限套娃的可调整参数有:角度,反向,轴向,速度运行时点击Test进行测试自己写的代码比较垃圾,命名与结构比较拉,高手轻点喷,新手有类似的需求可以拿去做参考上代码usingSystem.Collections;usingSystem.Collections.Generic;usingUnityEngine;u

  10. [Vuforia]二.3D物体识别 - 2

    之前说过10之后的版本没有3dScan了，所以还是9.8的版本或者之前更早的版本。 3d物体扫描需要先下载扫描的APK进行扫面。首先要在手机上装一个扫描程序，扫描现实中的三维物体，然后上传高通官网，在下载成UnityPackage类型让Unity能够使用这个扫描程序可以从高通官网上进行下载，是一个安卓程序。点到Tools往下滑，找到VuforiaObjectScanner下载后解压数据线连接手机，将apk文件拷入手机安装然后刚才解压文件中的Media文件夹打开，两个PDF图打印第一张A4-ObjectScanningTarget.pdf，主要是用来辅助扫描的。好了，接下来就是扫描三维物体。将瓶

随机推荐