循环移动数组元素

循环移动数组元素//循环移动数组元素//一种大部分数据只移动一次的算法//方法://  将数据循环移动,可以直接计算出每个数据的最终位置,直接移动即可//分析://  这种算法基本可看做每个数据只需要移动一次//  但是每个数据移动的位置需要计算,算法

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
 

// 循环移动数组元素
// 一种大部分数据只移动一次的算法
// 方法:
//   将数据循环移动, 可以直接计算出每个数据的最终位置, 直接移动即可
// 分析:
//   这种算法基本可看做每个数据只需要移动一次
//   但是每个数据移动的位置需要计算, 算法理解起来比较难, 实现也比较复杂
//   另外,由于总是间隔较远存取数据,在数据数量较大的时候会导致比较频繁缓存命中失败
//   常用的两次翻转算法,每个数据需要swap两次(平均每个移动3次),而且很容易理解,实现也简单

#include “stdafx.h”
#include <algorithm>
#include <iostream>

// 最大公约数
size_t gcd(size_t n, size_t m)
{

 if(n==0 || m == 0)
  return 0;

 while(true)
 {

  n %= m;
  if(n == 0)
   return m;
  std::swap(n, m);
 }
}

// 循环左移
template<typename T>
void CycleMove(T* data, size_t nLen, size_t nMov)
{

 if(data == 0 || nLen <= 1)
  return;

 nMov %= nLen;
 if(nMov == 0)
  return;

 // 分组处理
 size_t nGroup = gcd(nLen, nMov);
 // 每组数据数量
 size_t nGroupSize = nLen / nGroup;

 for(size_t i=0; i<nGroup; ++i)
 {

  // 保存第一个数
  T d0 =  data[i];
  size_t iPosD = 0;
  size_t iPosS = i;

  // 先移动nGroupSize-1个
  for(size_t j=1; j<nGroupSize; ++j)
  {

   // 数据位置
   iPosD = iPosS;
   iPosS += nMov;
   iPosS %= nLen;

   // 将数据左移
   data[iPosD] = data[iPosS];
  }
  // 将第一个放到最后
  data[iPosS] = d0;
 }
}

int _tmain(int argc, _TCHAR* argv[])
{

 char data[] = {-52, 83, 111, 103, 46, 115, 82, -111};
 size_t nNum = sizeof(data)/sizeof(data[0]);

 CycleMove(data, nNum,  3);

 for(size_t i=0; i<nNum; ++i)
 {

  std::cout << (int)data[i];
  if(i != nNum-1)
   std::cout << ” , “;
  else
   std::cout << std::endl;
 }

 return 0;
}

// 输出
// 103 , 46 , 115 , 82 , -111 , -52 , 83 , 111

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/159963.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号