首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

在C/C++中以递增的值对2D数组进行排序; 排序后知道原始位置?

在C/C++中,对2D数组进行排序并找到排序后的原始位置,可以通过以下步骤实现:

  1. 将2D数组转换为一维数组,并将数组元素及其原始位置存储在结构体中。
  2. 使用排序算法对一维数组进行排序。
  3. 根据排序后的数组元素在结构体中的位置,找到原始位置。

以下是一个示例代码:

代码语言:c++
复制
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

struct Element {
    int value;
    int row;
    int col;
};

bool compare(const Element &a, const Element &b) {
    return a.value < b.value;
}

int main() {
    int arr[3][3] = {
        {9, 4, 5},
        {7, 2, 1},
        {8, 3, 6}
    };

    vector<Element> elements;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            elements.push_back({arr[i][j], i, j});
        }
    }

    sort(elements.begin(), elements.end(), compare);

    for (const auto &e : elements) {
        cout << "Value: " << e.value << ", Original position: (" << e.row << ", " << e.col << ")"<< endl;
    }

    return 0;
}

输出结果:

代码语言:txt
复制
Value: 1, Original position: (1, 2)
Value: 2, Original position: (1, 1)
Value: 3, Original position: (2, 2)
Value: 4, Original position: (0, 1)
Value: 5, Original position: (0, 2)
Value: 6, Original position: (2, 0)
Value: 7, Original position: (1, 0)
Value: 8, Original position: (2, 1)
Value: 9, Original position: (0, 0)

这个示例代码首先将2D数组中的元素及其原始位置存储在一个结构体数组中,然后使用std::sort函数对结构体数组进行排序,最后输出排序后的结果及其原始位置。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

文心一言 VS 讯飞星火 VS chatgpt (73)-- 算法导论7.1 4题

如果要修改QUICKSORT使其以非递增序进行排序,可以考虑以下几种方法: 1.自定义比较函数 QUICKSORT使用的比较函数是比较数组中两个元素的值,然后根据它们的值来决定它们应该排在哪一组子序列里面...对于一个非递增的数组,原始的QUICKSORT将返回一个递增的排序结果(因为它总是选择最小值或最大值作为枢轴值)。而修改后的QUICKSORT则可以随机地选择枢轴值,因此可以得到一个非递增的排序结果。...在这里插入图片描述 chatgpt: 要修改快速排序算法以实现非递增排序,只需对原始的快速排序算法进行一些变动即可。...: 1.在 quicksort 函数中,修改递归调用的顺序,先对左子数组进行排序(quicksort(array, low, pivot - 1)),再对右子数组进行排序(quicksort(array...这将改变元素的处理顺序,使得数组以非递增序进行排序。 2.在 partition 函数中,将大于等于 pivot 的元素移到子数组的左侧。

15720

【初阶数据结构】打破递归束缚:掌握非递归版快速排序与归并排序

图片个人主页: 是店小二呀C语言笔记专栏: C语言笔记C++笔记专栏: C++笔记初阶数据结构笔记专栏: 初阶数据结构笔记喜欢的诗句:无人扶我青云志 我自踏雪至山巅一、非递归实现快速排序void...,基本思想是以某数值为基准值,不断将待排序集合分割成两组子序列,采用前序遍历的方法根 左子树 右子树,对于递归的过程中我们知道左子树会演变为新的根,也会分为新根 新左子树 新右子树,然后我们将采用栈来模拟递归的过程...基本思路:整个序列分为以**gap**为子序列,结束条件为gap 数组中,(子序列中只有一个数据时,默认是有序的)。...对于两个有序子序归并在一起,形成一个新的有序子序列,当形成完新的子序列,复制到原数组中,不断重复该操作。解决办法:对此应当设置变量gap为归并每组数据个数,首先gap设为1,以二的幂次方增长。...完成一趟for循环,需要拷贝到原数组中,这样子的话不参与进程的序列,将被随机值替代.if (end1 >= n || begin2 >= n) break;if (end2 >= n) end2 =

9610
  • 十大排序——最全最详细,一文让你彻底搞懂

    ,直到找到已排序的元素小于或者等于新元素的位置; 5.将新元素插入到该位置后; 6.重复步骤2~5。...因此,在调用一些函数或者使用STL的时候,记得看到优先队列,就知道是堆这样的结构。...堆排序的过程是弹出最大值。我们每次都把最大值放最后, // 得到的效果就是递增数组。...算法描述 1.找出待排序的数组中最大和最小的元素; 2.统计数组中每个值为i的元素出现的次数,存入数组C的第i项; 3.对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加); 4.反向填充目标数组...算法描述 1.取得数组中的最大数,并取得位数; 2.arr为原始数组,从最低位开始取每个位组成radix数组; 3.对radix进行计数排序(利用计数排序适用于小范围数的特点)。

    95021

    808《数据结构》参考答案

    答:程序如下所示: 思路提示:将10个数字先排序,若由小到大排序,则最大值和次大值分别对应排序后的数组中最后一个和倒数第二个;若由大到小排序,则最大值和最小值分别对应排序后的数组中第一个和第二个。...从键盘输入10个整数到一个一维数组,采用起泡排序法对这10个整数进行从小到大排序,输出排序结果。...二叉排序树的特点是,若左子树非空,则左子树上结点的值均小于根结点的值;若右子树非空,则右子树上结点的值均大于根结点的值。所以根据这一特点,可以看出二叉排序树的中序遍历是一个递增序列。...以二叉链表为存储结构,在二叉树中删除以值x为根结点的子树。 答:程序如下所示: 思路:对二叉链表进行遍历,在遍历的过程中查找结点x并记载其双亲,然后将结点x的双亲结点中指向结点x的指针置空。...假设顺序表L中的元素递增排列,设计算法在顺序表中插入元素x,要求插入后仍保持其递增有序性。

    70210

    笨办法学 Python · 续 练习 22:后缀数组

    我只是按顺序取下字符串的后缀,然后对列表进行排序。...一旦我有了这个列表,那么我可以通过这个列表的二分搜索,来找到我想要的任何后缀。这个例子很简陋,但是在实际的代码中,你可以很快地做到它,你可以跟踪所有的原始索引,所以你可以引用后缀的原始位置。...我跳起来走到白板,向那个家伙解释如何制作一个后缀树,它如何提高搜索性能,修改后的堆排序如何更快,后缀树的工作原理,为什么它比三叉搜索树更好,以及如何在 C 中实现。...他摇摇头,拿着他的东西,起身说:“好吧,我会让大家知道我的想法。” 几分钟后,下一个面试官来了。他抬头看着白板,笑了起来并嘲笑我,然后问我另一个 C++ 模板元编程问题,我无法回答。...该类将使用一个字符串,将其拆成后缀列表,然后对其进行以下操作: find_shortest 找到以它开始的最短子串。

    1K20

    c++期末总结

    0、c++期末总结 0.1、程序的构成 一个C++程序可以由一个程序单位或多个程序单位构成。每一个程序单位作为一个文件。在程序编译时,编译系统分别对各个文件进行编译,因此,一个文件是一个编译单元。...0.2、程序的编写与实践 用高级语言编写的程序称为“源程序”,C++的源程序是以.cpp作为后缀的 对源程序(.cpp)进行编译 ➡ 目标程序(.obj) ➡ 二进制文件(.exe) 编写C++程序一般需要经过的几个步骤是...; 注意: 两个整数相除结果依然是整数(这里不进行四舍五入,直接舍去小数点后面数字) C++中两个小数可以相除 运算的两个数中有一个数为float型数据,则运算的结果是double型,因为C++在运算时对所有...前置递增先对变量进行++,再计算表达式 后置递增先计算表达式,后对变量进行++ //递增 int main() { //后置递增 int a = 10; a++; //等价于a =...++,再计算表达式 int a2 = 10; int b2 = ++a2 * 10; cout << b2 << endl; //110 //后置递增先计算表达式,后对变量进行++ int

    14400

    云课五分钟-0B快速排序C++示例代码-注释和编译指令

    通过遍历每个网格单元,并对其进行DFS搜索,找到以当前网格单元为起点的最长递增路径。使用一个缓存数组 cache 来记录每个网格单元对应的最长路径长度,避免重复计算。...最终遍历整个网格后,找到最长路径的长度,即为结果。 您提供的代码是一个在二维矩阵中寻找最长递增路径的长度的问题。...其中,partition函数用来确定基准元素的位置,quickSort函数用来递归地对左右子序列进行排序。最终,程序输出排好序的数组。...获取数组长度 int n = arr.size(); // 对数组进行快速排序 quickSort(arr, 0, n - 1); // 打印排序后的数组元素 for (auto i : arr...使用for_each()函数来遍历和打印数组元素,这是C++98中提供的一种遍历容器的方法。这里还使用了lambda表达式作为函数参数,以简化代码。

    17810

    深入探讨C++中的双向链表:构建高效数据结构的关键方法与实用技巧(上)

    因此,让我们一起探索std::list的奥秘,领略其在C++编程中的独特魅力吧!...反转和排序: reverse();:反转链表。 sort();:对链表中的元素进行排序。...⚽三、list的迭代器 在C++中,std::list的迭代器提供了对链表元素进行遍历的能力,但由于std::list是双向链表,其迭代器是双向迭代器,不支持随机访问。...⚽四、list的元素访问 在C++的std::list容器中,元素的访问方式与数组或std::vector等序列容器有所不同,因为std::list是一个双向链表。...⚽七、list的排序 7.1 排序 在C++中,std::list容器支持排序操作,但它不提供像std::sort这样的通用排序函数(因为std::sort需要随机访问迭代器,而std::list只提供双向迭代器

    11610

    【初阶数据结构篇】归并排序、计数排序

    别忘了点赞、收藏并分享给更多的小伙伴哦!你们的支持是我不断进步的动力! 分享给更多人:如果你觉得这篇文章对你有帮助,欢迎分享给更多对C++感兴趣的朋友,让我们一起进步! 1....合并思想:对两个数组的元素进行合并 注意:我们应另外创建一个数组存储排序后的结果,会覆盖原始数值。...但问题是这需要事先知道关键字的分布情况 适合查找表较小且连续的情况 由于这样的限制,在现实应用中,此方法虽然简单,但却并不常用 2.1 分析 步骤: 第一步,确定数组最大值和最小值,...遍历 第二步,申请空间并初始化 第三步,统计每个数据出现的个数 根据申请的数组下标递增依次往原数组放数据 将对应下标加上min就是原始数据,数组下标对应的值出现几次就说明该数出现几次。...排序算法复杂度及稳定性分析 稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的 相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,⽽在排序后的序列中

    6410

    数据结构与算法之三 深入学习排序

    在快速排序算法中,你: 从名为​枢轴 的列表处选择元素 。...QuickSort(J + 1, high)​//​​对枢轴右侧的列表应用快速排序​ 此排序算法的总时间取决于枢轴值的位置。 最糟的情形出现在列表已经排序时。...将 arr[i] 存储到数组 B 中的索引 k 处   ii. 按 1 递增 i   iii. 按 1 递增 k 5....将排序的数组 B 中的所有元素复制到原始数组 arr 中 若要排序此列表,您需要按递归方式将列表划分为两个几乎完全相等的子列表,直 到每个子列表仅包含一个元素。  ...使用相同的算法排序列表的两个部分。 答案: 快速排序 ​小结​​ ​在本章中,你已经学到: 快速排序和归并排序算法基于分治技巧。 若要通过使用快速排序算法来排序项目列表,您需要: 选择枢轴值。

    10910

    算法和数据结构:归并排序

    合并排序最大的优点是它的时间复杂度为O(nlgn),这个是我们之前的选择排序和插入排序所达不到的。他还是一种稳定性排序,也就是相等的元素在序列中的相对位置在排序前后不会发生变化。...设定两个指针,最初位置分别为两个已经排序序列的起始位置 比较复制数组中两个指针所指向的元素,选择相对小的元素放入到原始待排序数组中,并移动指针到下一位置 重复步骤3直到某一指针达到序列尾 将另一序列剩下的所有元素直接复制到原始数组末尾...array, lo, mid, hi);//对左右排好的序列进行合并 } ... } 以排序一个具有15个元素的数组为例,其调用堆栈为: ?...并行化 分治算法通常比较容易进行并行化,在浅谈并发与并行这篇文章中已经展示了如何对快速排序进行并行化(快速排序在下一篇文章中讲解),合并排序一样,因为我们均分的左右两侧的序列是独立的,所以可以进行并行,...在Java中对引用对象进行排序,Perl、C++、Python的稳定性排序的内部实现中,都是使用的合并排序。

    39530

    盛算信息-面试经历-笔试部分-完整题目(一)

    static与const的含义和作用 C++中static:首先他的作用是定义静态变量 在函数内部声明的静态变量具有静态存储持续时间,他们在程序执行期间保持存在,而不是在每次函数调用时创建和销毁,静态变量在函数调用之间保持其值不变...= new Circle(5.0); // 输出 "Static initializer block executed" } C++中const:在C++中,const关键字用于声明常量,表示该变量的值在初始化后不能被修改...当我们将一个对象作为参数传递给方法时,实际上是将对象的引用传递给了方法。这意味着在方法内部对参数的修改会影响到原始对象。...然后对这两部分分别进行递归排序。通过不断地划分和排序,最终实现整个数组的排序。 时间复杂度:平均情况下的时间复杂度为O(nlogn),最坏情况下的时间复杂度为O(n^2)。...来源:快速排序是由冒泡排序改进而来的,它采用了分治法的思想,通过选择一个基准元素将数组分为两部分,然后对这两部分进行递归排序。

    6210

    算法:排序

    经过如此一趟排序,使得 个元素中值最大元素被安置在序列的第 个位置上; 此后,再对前 个元素进行同样过程,使得该 个元素中值最大元素被安置在第 然后再对前 个元素重复上述过程,...这 说明选择排序法所进行的元素之间的比较次数与序列的原始状态无关,同时可以确定算法的时间复杂度为 由于我们进行交换元素时是在不相邻的元素之间进行的,因此很有可能会改变值相同元素的前后位置,因此,选择排序法是一种非稳定性排序算法...对于具有n个元素的序列,插入排序算法一共要进行n-1趟排序 当原始序列是按值递增序列(升序)时,对应的每个i值只进行一次元素之间的比较,因而总的比较次数最少,为 ,并不需要移动元素(记录),这是最好的情况最...下面以最低位优先法为例,讲解一下算法步骤 遍历数组元素,获取数组最大值元素,并取得位数 以个位元素为索引,对数字元素排序 合并数组 之后依次以十位,百位,...直到最大值元素的最高位处值为索引,进行排序...给定单个链表的头 head ,使用 插入排序 对链表进行排序,并返回 排序后链表的头 。

    1.2K20

    回溯算法:递增子序列

    数组中的整数范围是 [-100,100]。 给定数组中可能包含重复数字,相等的数字应该被视为递增的一种情况。 思路 这个递增子序列比较像是取有序的子集。而且本题也要求不能有相同的递增子序列。...在回溯算法:求子集问题(二)中我们是通过排序,再加一个标记数组来达到去重的目的。 而本题求自增子序列,是不能对原数组进行排序的,排完序的数组都是自增子序列了。 「所以不能使用之前的去重逻辑!」...「本题只要同层重复使用元素,递增子序列就会重复」,而回溯算法:求子集问题(二)中是排序之后看相邻元素是否重复使用。...最后整体C++代码如下: C++代码 // 版本一 class Solution { private: vector> result; vector path...程序运行的时候对unordered_set 频繁的insert,unordered_set需要做哈希映射(也就是把key通过hash function映射为唯一的哈希值)相对费时间,而且每次重新定义set

    1.2K20

    DP:子序列模型

    len[i]表示以i位置为结尾的所有子序列中,最长递增子序列的“长度” count[i]表示以i位置为结尾的所有子序列中,最长递增子序列的“个数” 2、状态转移方程 nums[j]<nums[i]时.... - 力扣(LeetCode) 算法原理: 预处理:由于题目要求是任意顺序组成数链对,所以我们在处理的时候不仅要考虑前面,还要考虑后面,这样不利于我们的动态规划表示,所以我们要先按照第一个元素进行排序...(比如[a,b] [c,d],aca,所以后面的不需要考虑到),我们要进行sort,在C++中,vector、pair的默认比较逻辑都是按照字典序的,恰好符合我们的要求,所以我们可以直接调用...1、状态表示(经验+题目要求) dp[i]表示以i位置为结尾所有数对链序列中,最长数对链的长度。...,到时候在找的时候还得判断bc的情况) (2)先固定倒数第二个数,再枚举最后一个数(可以等i位置填完后再将i的位置丢进哈希表,这样可以保证哈希表内的元素的下标必然是小的,就可以不需要判断bc

    10110

    9.1 C++ STL 排序、算数与集合

    C++ STL(Standard Template Library)是C++标准库中的一个重要组成部分,提供了丰富的模板函数和容器,用于处理各种数据结构和算法。...sort函数将[first, last]范围内的元素按照递增顺序排序,并将排序后的结果存储在相同的容器中。sort函数在执行前,需要保证所排序的元素类型支持的元素按照递增顺序排序,并保证相等元素的相对顺序不变,将排序后的结果存储在相同的容器中。...merge函数将已排序的两个序列按照递增顺序合并成一个新的有序序列,输出到result所指向的迭代器位置,并将输出结果的尾后迭代器作为函数的返回值返回。...另外,为了实现更高效的运行时间,C++ STL中提供了另一个函数模板来查找最大或最小值。

    22130

    9.1 C++ STL 排序、算数与集合

    C++ STL(Standard Template Library)是C++标准库中的一个重要组成部分,提供了丰富的模板函数和容器,用于处理各种数据结构和算法。...sort函数将[first, last]范围内的元素按照递增顺序排序,并将排序后的结果存储在相同的容器中。sort函数在执行前,需要保证所排序的元素类型支持的元素按照递增顺序排序,并保证相等元素的相对顺序不变,将排序后的结果存储在相同的容器中。...merge函数将已排序的两个序列按照递增顺序合并成一个新的有序序列,输出到result所指向的迭代器位置,并将输出结果的尾后迭代器作为函数的返回值返回。...另外,为了实现更高效的运行时间,C++ STL中提供了另一个函数模板来查找最大或最小值。

    19220

    四种简单的排序算法

    swap()方法则用于交换数组中的两条记录,也对交换数进行了打印(这里我注释掉了,但在测试时可以取消对它们的注释)。外层for循环控制变量i表示当前处理第i条记录。...我们来对它进行一个考察,按照这种排序方式,在进行完第一趟循环之后,最小的一定位于数组最顶部(下标为0);第二趟循环之后,次小的记录位于数组第二(下标为1)的位置;依次类推,第n-1趟循环之后,第n-1小的记录位于数组第...swap(a[j], a[j-1]); } } } 3.选择排序 算法思想 选择排序是对冒泡排序的一个改进,从上面冒泡排序的输出可以看出,在第一趟时,为了将最小的值13由数组末尾冒泡的数组下标为...在第i趟时,搜索数组的n-i+1个记录,寻找最小的记录(对于整个数组来说则是第i小的),然后放在数组i-1的位置(注意数组以0起始)。可以看出,选择排序显著的减少了交换的次数。...这里要注意的是分组中记录在原数组中的位置,以第2个分组{14,20}来说,它的下标是(1,5),所以这两个记录在原数组的下标分别为a[1]=14;a[5]=20。

    61520

    寻找旋转排序数组中的最小值

    描述: 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 ( 例如,数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 请找出其中最小的元素。..., 比较次数 o(n) 执行用时: 28 ms, 在Find Minimum in Rotated Sorted Array的C++提交中击败了2.89% 的用户 第二次尝试:减少比较次数 对一个数组进行折半拆分...执行用时: 4 ms, 在Find Minimum in Rotated Sorted Array的C++提交中击败了98.16% 的用户 3. c++ /** Time complexity...寻找旋转排序数组中的最小值 假设按照升序排序的数组在预先未知的某个点上进行了旋转。 请找出其中最小的元素。期望:请找出其中最小的元素 拦路虎: 1....如果是完全升序 第一数字就是 , 旋转数值是升序(相邻的元素都是递增), 根本不知道抄那个方向移动?炸锅了。 肯定没有那么容易赛。 2.

    71400

    最高频元素的频数(二分查找)

    题目 元素的 频数 是该元素在一个数组中出现的次数。 给你一个整数数组 nums 和一个整数 k 。 在一步操作中,你可以选择 nums 的一个下标,并将该下标对应元素的值增加 1 。...执行最多 k 次操作后,返回数组中最高频元素的 最大可能频数 。...4 是数组中最高频元素,频数是 2 。 - 对第二个元素执行 4 次递增操作,此时 nums = [1,8,8,13] 。 8 是数组中最高频元素,频数是 2 。...解题 对数字进行排序(只有小的数能通过操作变成大的数),并求前缀和 二分求解最大频次 每次二分的时候,遍历一次前缀和数组,以某位置为最大频数的数字,能不能满足要求?...ms 84 MB C++ ---- 我的CSDN博客地址 https://michael.blog.csdn.net/ 长按或扫码关注我的公众号(Michael阿明),一起加油、一起学习进步!

    43020
    领券